Q:

# 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

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,

• Declare two variables curmax=0 and max_sofar=-1
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 for
```
• Now, if there is at least one '0'
The minimum result will be 1 (We will consider '0' as minimum possible substring)
So, if