Last Updated: 25 Feb, 2021
Maximum Difference Of Zeros And Ones In A Binary String
Moderate
Asked in companies
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
Approaches
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) :
- Initialize a variable ‘currentCount’ with 0, which counts the difference between the number of zeros and the number of ones in that substring.
- Iterate from k = j to k = I:
- If the character at the kth index is ‘0’, then increment the variable ‘currentCount’.
- Otherwise, decrement ‘currentCount’.
- If currentCount is greater than maximumCount, then update the maximumCount.
- 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) :
- 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.
The idea is to assign values to ‘0’s and ‘1’s virtually. We are assigning the value of every ‘0’ as 1, and the value of every ‘1’ as -1 since every ‘0’ will contribute 1 and every ‘1’ will contribute -1 to the answer in any substring. Hence, we are keeping the value of ‘0’ as positive and ‘1’ as negative. We are not changing the string or using a new array to store the weights. In the run time, when we’ll come across any ‘0’ or ‘1’, we’ll add or subtract according to the assigned weights.
- Initialize two variables ‘maximumCount’ with 0, which stores the maximum difference between the number of zeros and the number of ones, and ‘currentCount’ with 0, which stores the difference between the number of zeros and the number of ones in the current substring.
- Iterate from i = 0 to N - 1:
- If the current character is ‘0’, then add increment the currentCount. Else decrement the currentCount.
- If the currentCount becomes negative, then set it as 0 as we want to maximize the difference. This is optimal because it is better to ignore any prefix of a substring that has a negative difference.
- 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.
- Else return the maximumCount.