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

mahmoud2506

Save to bookmark

2022-04-29

359

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.

C++ programming, Interview questions, C++ programming Interview-questions,

All Answers

mahmoud2506

2022-04-29

need an explanation for this answer? contact us directly to get an explanation for this answer

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
need an explanation for this answer? contact us directly to get an explanation for this answer

total answers (1)

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

All Answers

This question belongs to these collections

Similar questions

need a help?

find thousands of online teachers now