Find Length of longest substring with all 1's in a binary string with k queries

Question

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)

Answer 1

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.