Find the Longest Balanced Substring of a Binary String

Difficulty: Easy | Acceptance: 46.50% | Paid: No Topics: String

You are given a binary string s. A substring is balanced if it has an equal number of 0’s and 1’s, and all the 0’s and all the 1’s in these substrings are grouped consecutively.

Substrings that are balanced:

• “0101” is not balanced because the 0’s and 1’s are not grouped consecutively.
• ”0011” is balanced because the 0’s and 1’s are grouped consecutively, and their count is equal.
• ”0110” is not balanced because the 0’s and 1’s are not grouped consecutively.

Return the length of the longest balanced substring of s.

• Examples
• Constraints
• Brute Force
• Linear Scan

Examples

Example 1:

Input: s = "01000111"
Output: 6
Explanation: "000111" is the longest balanced substring with equal number of 0's and 1's and grouped consecutively.

Example 2:

Input: s = "00111"
Output: 4
Explanation: "0011" is the longest balanced substring.

Example 3:

Input: s = "111"
Output: 0

Constraints

1 <= s.length <= 100
s[i] is '0' or '1'.

Brute Force

Intuition We can check every possible substring of the binary string to see if it is balanced. A substring is balanced if it consists of some number of 0s followed by the same number of 1s.

Steps

• Iterate through all possible starting indices of the substring.
• For each starting index, iterate through all possible ending indices.
• For each substring defined by the start and end indices, check if it is balanced:
  • It must start with 0s.
  • Once a 1 is encountered, no 0s can follow.
  • The count of 0s must equal the count of 1s.
• Keep track of the maximum length found.

class Solution:
    def findTheLongestBalancedSubstring(self, s: str) -> int:
        res = 0
        n = len(s)
        for i in range(n):
            zeros = 0
            ones = 0
            valid = True
            for j in range(i, n):
                if s[j] == '0':
                    if ones > 0:
                        valid = False
                        break
                    zeros += 1
                else:
                    ones += 1
                if zeros == ones:
                    res = max(res, zeros + ones)
        return res

Complexity

• Time: O(n³) - We iterate O(n²) substrings and validation can take O(n) in the worst case.
• Space: O(1) - We only use a few variables for counting.
• Notes: This approach is simple but inefficient for large strings. Given the constraint n <= 100, it passes, but we can do better.

Linear Scan

Intuition We only need to track consecutive groups of 0s followed by 1s. As we iterate through the string, we count consecutive 0s. When we encounter a 1, we start counting consecutive 1s. The length of the balanced substring formed by these groups is limited by the smaller count (2 * min(zeros, ones)). If we encounter a 0 after counting 1s, the previous pattern is broken, so we reset our counters.

Steps

• Initialize zeros and ones counters to 0, and res to 0.
• Iterate through each character in the string:
  • If the character is ‘0’:
    • If we were previously counting 1s (ones > 0), it means the pattern “0…1…0” occurred. Reset zeros and ones to 0.
    • Increment zeros.
  • If the character is ‘1’:
    • Increment ones.
  • If zeros >= ones, we have a valid balanced prefix of the current segment. Update res with 2 * ones.
• Return res.

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

Complexity

• Time: O(n) - We traverse the string exactly once.
• Space: O(1) - We only use a few integer variables.
• Notes: This is the optimal solution for this problem.