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++) {
        //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





Comments and Discussions

Ad: Are you a blogger? Join our Blogging forum.





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


© https://www.includehelp.com some rights reserved.