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.
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.
The 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