0
$\begingroup$

Given a string of size n consisting of 0s and/or 1s.you have to perform k queries and there are two types of queries possible.

  1. "1"(without quotes): Print length of the longest substring with all '1'.
  2. "2 X"(without quotes): where X is an Integer between 1 to n.In this query, you will change character at Xth position to '1' (it is possible that the character at ith position was already '1')

Input Format:

  • First Line of input contains n and k, where n is string length and k is the number of queries.
  • Next line contains a string of 0's and/or 1's of length n.
  • Each of next k lines contains query of any one type (i.e 1 or 2).

Output Format: For each query of type 1, print in new line the maximum size of subarray with all 1's.

     Example Input:                        Example Output:
     5 7                                   0
     00000                                 1
     1                                     1
     2 3                                   3
     1                                     
     2 5
     1
     2 4
     1

My Solution: O(k*n) (if most of the queries of type 1)

 if(type==1){
        int count=0, ans=0;
        for(int i=0;i<str.size();i++){  //longest len substring
            if(str[i]=='1'){
                count++;
            }else{
               ans=max(ans,count);
               count=0;
            }
        }

        printf("%d\n",ans);
 }else{
        int xth;
        scanf("%d",&xth);
        str[xth-1]='1';   //update
 }

I am not able to figure out an efficient solution, as for 'type 1' query only solution I could think of is to iterate through string every time and maintain a "count" variable with all 1's consecutively and finally update "ans" variable when ith str becomes '0'.

I am thinking of using segment tree but don't know how to do. As required good solution should be O(k*log(n)) (doing "type1" query in log(n) time)

$\endgroup$
1
$\begingroup$

Observation: Type 2 query can only make the longest substring of 1 longer.

Let's call a substring of 1's a component. For example, there are 3 components in this string

1 1 1 0 0 1 0 1 1 1 1 0

When a 0 is changed to 1, only the components to its immediate left and right will be affected. The length of the other components remains the same.

string: 1 1 1 0 0 1 0 1 1 1 1 0
size  : 3 3 3 0 0 1 0 4 4 4 4 0

update position 7 to 1 (1-index)
string: 1 1 1 0 0 1 1 1 1 1 1 0
size  : 3 3 3 0 0 6 6 6 6 6 6 0

Hence, all you need to do is to keep track of the size of each component and merge them when necessary. You can do so using a Union-Find Disjoint Set data structure. You can have a variable to keep track of the size of the largest component and update its value if, after the merge, you get a larger component.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.