# Maximum difference of zeros and ones in binary string

Here, we are going to see how efficiently we can solve the problem to find maximum difference of zeros and ones in binary string using kadane's algorithm?
Submitted by Radib Kar, on June 02, 2020

Problem statement:

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

Solution Approach:

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 𝑚𝑎𝑥_𝑠𝑜𝑓𝑎𝑟 is finally updated as 0, that means all the characters are 1, there is no character '0'. Then we will return -1, else return 𝑚𝑎𝑥_𝑠𝑜𝑓𝑎𝑟

Let's check one example to fully understand how the algorithm works

```Let's the string be "0100100"
So
i=0
Curmax=1
Max_sofar updated to 1

i=1
Curmax=0
Max_sofar not updated ,still 1

i=2
Curmax=1
Max_sofar not updated,still  1

i=3
Curmax=2
Max_sofar updated to 2

i=4
Curmax=1 (2-1)
Max_sofar not updated,still 2

i=5
Curmax=2
Max_sofar not updated,still 1

i=6
Curmax=3
Max_sofar updated to 3

Final result is 3 that's why
```

C++ Implementation:

```#include <bits/stdc++.h>
using namespace std;

int maxdiff(string s)
{

int curmax = 0;
int max_sofar = -1;

for (int i = 0; i < s.length(); i++) {
if (s[i] == '0')
curmax++;
else
curmax--;
if (curmax < 0)
curmax = 0;
if (curmax > max_sofar)
max_sofar = curmax;
}
return max_sofar == 0 ? -1 : max_sofar;
}

int main()
{

string s;
cout << "Enter string:\n";
cin >> s;

cout << "Max difference between 0 and 1 in any substring: " << maxdiff(s) << endl;

return 0;
}
```

Output:

```Enter string:
001100010
Max difference between 0 and 1 in any substring: 3
```

Languages: » C » C++ » C++ STL » Java » Data Structure » C#.Net » Android » Kotlin » SQL
Web Technologies: » PHP » Python » JavaScript » CSS » Ajax » Node.js » Web programming/HTML
Solved programs: » C » C++ » DS » Java » C#
Aptitude que. & ans.: » C » C++ » Java » DBMS
Interview que. & ans.: » C » Embedded C » Java » SEO » HR
CS Subjects: » CS Basics » O.S. » Networks » DBMS » Embedded Systems » Cloud Computing
» Machine learning » CS Organizations » Linux » DOS
More: » Articles » Puzzles » News/Updates