Home » Interview coding problems/challenges

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 [Last updated : March 20, 2023]

Problem Description

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 of Maximum difference of zeros and ones in binary string

#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++) {
        //similar approach to kadanes algo
        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

---