Maximum Difference Of Zeros And Ones In A Binary String

Posted: 25 Feb, 2021
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

You are given a binary string. You are supposed to find the maximum difference between the number of zeros(0's) and the number of ones(1's) in any substring of the given string.

Note:
Binary String is a string that consists of only ‘0’s and ‘1’s.

A string ‘A’ is said to be a substring of string ‘B’ if ‘A’ can be obtained by deleting several characters(possibly none) from the start of ‘B’ and by deleting several characters(possibly none) from the end of ‘B’.

The substring must have a length greater than or equal to 1.
Input Format:
The first line of input contains an integer ‘T’, denoting the number of test cases. The test cases follow.

The first line of each test case contains a binary string.
Output Format:
Print the maximum difference between the number of zeros and the number of ones in any substring of the given string.

Print the output of each test case in a new line.
Constraints:
1<= T <= 100
1 <= |S| <= 10,000
S[i] = ‘0’ / ‘1’

Time Limit: 1 sec
Approach 1

The idea is to check all the possible substrings and count the difference between the number of zeros and the number of ones in every substring.

 

  • Initialize a variable ‘maximumCount’ with 0, which stores the maximum difference between the number of zeros and the number of ones.
  • Iterate from i = 0 to N - 1:
    • Iterate from j = 0 to j = i ( this step is fixing the left index and right index of the string, which forms a substring, i.e., j becomes the leftmost index and i becomes the rightmost index of the substring) :
      1. Initialize a variable ‘currentCount’ with 0, which counts the difference between the number of zeros and the number of ones in that substring.
      2. Iterate from k = j to k = I:
        • If the character at the kth index is ‘0’, then increment the variable ‘currentCount’.
        • Otherwise, decrement ‘currentCount’.
      3. If currentCount is greater than maximumCount, then update the maximumCount.
  • Before returning the final answer, check if the maximumCount is positive or not,
    • If the maximumCount is zero, it means that there are only 1’s in the string. In this condition, return -1 as expected in the output.
    • Otherwise, return the maximumCount.
Try Problem