Click here to Skip to main content
15,748,749 members
Please Sign up or sign in to vote.
1.00/5 (1 vote)
See more:
Given a string of size n consisting of 0s and/or 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
     2 5
     2 4

What I have tried:

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

        int count=0, ans=0;
        for(int i=0;i<str.size();i++){  //longest len substring

        int 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)
PIEBALDconsult 2-Dec-17 10:34am    
Define and implement a data structure that will maintain the information you need.
I would imagine a form of lookup table -- indexed by character (0,1) -- of maps that contain a start index and a length.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900