Maximum Difference Of Zeros And Ones In A Binary String

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
14 upvotes
Asked in companies
D.E.ShawAmdocs

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
1100010001
1101
Sample Output 1:
5
1
Explanation For Sample Input 1:
In the first test case, the binary string is ‘1100010001’. To find out the maximum difference between the number of zeros and the number of ones in the substring of the string, We have a substring from index 2 to 8, which consists of all ‘0’s except the 5th index, which is ‘1’. So, the answer is 6 - 1 = 5.

In the second test case, the binary string is ‘1101’. To find out the maximum difference between the number of zeros and the number of ones in the substring of the string, We have a substring from index 2 to 2(length = 1), which consists of one ‘0’s and zero ‘1’s, So, the answer is 1 - 0 = 0.
Sample Input 2:
2   
000000
0101010101
Sample Output 2:
6
1
Hint

Make all the possible substrings and then count the maximum difference between the number of zeros and the number of ones in the substring of the string.

Approaches (2)
Brute Force

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.
Time Complexity

O(|S| ^ 3), where |S| is the length of the given string.

 

As we are iterating having two loops for fixing the leftmost and the rightmost index of the substring and one more for counting the answer of the current substring. Hence, the overall time complexity is O(|S| ^ 3).

Space Complexity

O(1)

 

As we are using constant space.

Code Solution
(100% EXP penalty)
Maximum Difference Of Zeros And Ones In A Binary String
Full screen
Console