You are given a binary string (containing character 0 and 1 only) s of length n. You task is to convert all the 1s in this string to 0. To do this you can do the following :
First choose an integer K and then perform the following operation any number of times :
- Choose any substring of this string such that length of substring is greater than or equal to K and change all 0s to 1 and all 1s to 0 in that substring i.e. for a substring [L,R] (R-L+1>=K) in s, for each i such that L<=i<=R, if si is 0 make it 1 and if it is 1 make it 0.
Find the maximum integer K less than or equal to n that we can choose such that it is possible to convert the string to all 0s using above method.
Constraints
1<=n<=100000
Examples
Input : 101 Output : 2 Explanation : If we choose K = 2, we can convert the string to all 0s by following way - choose substring [0,1] = "10", then s becomes 011
- now choose substring [1,2] = "11", then s becomes 000
It is the maximum K as we can not convert the sting to all 0s by choosing K = 3.
Input : 10000 Output : 4 Explanation : We can choose K = 4 and convert the following way - Choose substring [0,4] = "10000", the s becomes 01111
- Choose substring [1,4] = "1111", then s becomes 00000
Input/Output - [execution time limit] 4 seconds (py3)
- [input] string s given binary string
- [output] integer Output the maximum K such that it is possible to convert s to all 0s by the operation.
can someone please tell me how to solve this problem
Comments (1)