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"(without quotes): Print length of the longest substring with all '1'.
- "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)