Teaching Kids Programming – Find the Longest Balanced Substring of a Binary String

Teaching Kids Programming: Videos on Data Structures and Algorithms

You are given a binary string s consisting only of zeroes and ones. A substring of s is considered balanced if all zeroes are before ones and the number of zeroes is equal to the number of ones inside the substring. Notice that the empty substring is considered a balanced substring. Return the length of the longest balanced substring of s. A substring is a contiguous sequence of characters within a string.

Example 1:
Input: s = “01000111”
Output: 6
Explanation: The longest balanced substring is “000111”, which has length 6.

Example 2:
Input: s = “00111”
Output: 4
Explanation: The longest balanced substring is “0011”, which has length 4.

Example 3:
Input: s = “111”
Output: 0
Explanation: There is no balanced substring except the empty substring, so the answer is 0.

Constraints:
1 <= s.length <= 50
‘0’ <= s[i] <= ‘1’

Find the Longest Balanced Substring of a Binary String

This is a problem that asks us to find the length of the longest balanced substring in a given string s. A balanced substring is one in which the number of ‘0’s and ‘1’s are equal. In other words, the substring has an equal number of zeros and ones. And one additional requirement is that the zero(s) has/have to come before one(s).

We can bruteforce all substrings (size of even, as odd-length substrings can not be balanced), and then check each even-size substring to see if it is a balanced substring. Bruteforce all pairs of even-length substrings require O(N^2) time, and the additional checking takes O(N) – resulting in overall O(N^3) time solution.

Let’s take a look at the following optimal solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution:
    def findTheLongestBalancedSubstring(self, s: str) -> int:
        ans = 0
        ones = 0
        zeros = 0
        prev = None
        for i in s:
            if i == '1':
                ones += 1
                if zeros >= ones:
                    ans = max(ans, ones * 2)
            else:
                if prev == '0':                
                    zeros += 1
                else:
                    zeros = 1
                ones = 0
            prev = i
        return ans

class Solution:
    def findTheLongestBalancedSubstring(self, s: str) -> int:
        ans = 0
        ones = 0
        zeros = 0
        prev = None
        for i in s:
            if i == '1':
                ones += 1
                if zeros >= ones:
                    ans = max(ans, ones * 2)
            else:
                if prev == '0':                
                    zeros += 1
                else:
                    zeros = 1
                ones = 0
            prev = i
        return ans

The Python solution provided uses a simple approach to solve the problem. The solution traverses the given string s from left to right, keeping track of the number of ones and zeros encountered so far. Whenever a ‘1’ is encountered, the number of ones is incremented, and if the number of zeros encountered so far is greater than or equal to the number of ones, the length of the current balanced substring is calculated as ones * 2. This is because a balanced substring will have an equal number of ones and zeros, and hence the length will be twice the number of ones.

Whenever a ‘0’ is encountered, the number of zeros is incremented. If the previous character was also ‘0’, then the current ‘0’ is part of a new substring, and the count of zeros is reset to 1. The count of ones is reset to 0 whenever a ‘0’ is encountered.

Finally, the length of the longest balanced substring encountered so far is returned.

We can save and update the “previous” character, alternatively, we can use enumerate function and then be able to index the previous character.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution:
    def findTheLongestBalancedSubstring(self, s: str) -> int:
        ans = 0
        ones = 0
        zeros = 0
        for j, i in enumerate(s):
            if i == '1':
                ones += 1
                if zeros >= ones:
                    ans = max(ans, ones * 2)
            else:
                if j == 0 or s[j - 1] == '0':
                    zeros += 1
                else:
                    zeros = 1
                ones = 0
        return ans

class Solution:
    def findTheLongestBalancedSubstring(self, s: str) -> int:
        ans = 0
        ones = 0
        zeros = 0
        for j, i in enumerate(s):
            if i == '1':
                ones += 1
                if zeros >= ones:
                    ans = max(ans, ones * 2)
            else:
                if j == 0 or s[j - 1] == '0':
                    zeros += 1
                else:
                    zeros = 1
                ones = 0
        return ans

Let’s consider an example to understand the solution better. Suppose we have the input string s = “11001100”. The solution starts by initializing the variables ans, ones, and zeros to 0. Then it starts traversing the string from left to right.

1. The first character encountered is ‘1’, so the count of ones is incremented to 1. The zero count is zero.
2. The second character is also ‘1’, so the count of ones becomes 2. Since no ‘0’ has been encountered so far, the current substring is not balanced yet, and the solution moves to the next character.
3. The third character is ‘0’, so the count of zeros is incremented to 1. The count of ones is reset to 0 since a ‘0’ has been encountered.
4. The fourth character is also ‘0’, so the count of zeros becomes 2.
5. The fifth character is ‘1’, so the count of ones is incremented to 1. Since the number of zeros encountered so far is equal to the number of ones, the length of the current balanced substring is calculated as ones*2=2.
6. The sixth character is also ‘1’, so the count of ones becomes 2. And the number of zeros (2) is equal or larger than the number of ones (2), and thus we can make a balanced substring 2*2=4.
7. The seventh character is ‘0’, so the count of ones is reset to 0 since a ‘0’ has been encountered. One is reset to zero.
8. The eighth character is also ‘0’, so the count of zeros becomes 2. And one again is reset to zero.

After traversing the entire string, the length of the longest balanced substring encountered so far is 2×2=4, which is returned by the solution.

The time complexity of this solution is O(n), where n is the length of the input string s, since it traverses the string only once. The space complexity of the solution is O(1), since it uses a constant amount of extra space to store the variables ans, ones, and zeros.

Conclusion

In conclusion, the provided Python solution is a simple and efficient way to solve the problem of finding the length of the longest balanced substring in a given string s. The approach taken is intuitive and easy to understand, and the time and space complexity are both optimal. Overall, this is a great solution for this problem, and it can be used as a reference for similar problems in the future.

–EOF (The Ultimate Computing & Technology Blog) —