Given a binary string of 0s and 1s. Find the maximum difference of number of 0s and number of 1s (number of 0s – number of 1s) in substrings of the string.
Input:
Input is a string str
Output:
For each test case,
print the maximum difference.
If there is no 0 in the entire string, print "-1".
Explanation of Example:
Input:
1100010001
Output:
5
Explanation:
The substring to be considered will be "0001000"
where number of 0's are 6 and number of 1's are 1
So difference is 5 and it is maximum.
For any other substring the difference is less than 5
Input:
111
Output:
-1
Explanation:
Since, all the characters of the string is '1'
there is no '0'. Hence, the output is -1.
C++ programming
The solution approach for the above problem is like Kadane's algorithm
The algorithm is like below,
curmax will keep track for local maximum difference and max_sofar is basically for final global solution.
for i=0 to s.length() if(s[i]=='0') //if current character is 0 curmax++; //increase the current difference else curmax--; //decrease the current difference if(curmax<0) //if local difference goes down negative curmax=0; //discard up to this substring if(curmax>max_sofar) //update global value if possible max_sofar=curmax; end forThe minimum result will be 1 (We will consider '0' as minimum possible substring)
So, if need an explanation for this answer? contact us directly to get an explanation for this answer