LeetCode Solutions Blog

Find the Longest Balanced Substring of a Binary String

Number: 2723

Difficulty: Easy

Paid? No

Companies: Tinkoff

Problem Description

Given a binary string s, find the longest substring where all 0's come before 1's and the number of 0's equals the number of 1's. The substring must be contiguous, and if no such non-empty substring exists, return 0.

Key Insights

The balanced substring must be of the form "0...0 1...1" (first all 0's, then all 1's).
The number of 0's and 1's in the substring must be equal.
One can partition the string into contiguous groups of identical characters.
For each adjacent pair of groups where the first group is '0' and the second is '1', the maximum balanced substring length is 2 * min(group1_length, group2_length).

Space and Time Complexity

Time Complexity: O(n) where n is the length of the string, since we make a single pass to group characters and another pass over the groups. Space Complexity: O(n) in the worst-case scenario for storing the groups.

Solution

The solution involves scanning the string and grouping consecutive equal characters along with their counts. Once the groups are formed, iterate through adjacent groups. For each adjacent pair where the first group is '0' and the second is '1', compute a candidate balanced substring length as 2 * min(count of 0's, count of 1's). Keep track of the maximum candidate found, and return it as the answer. This efficiently finds the longest balanced substring meeting the given conditions.

Code Solutions

# Python solution with detailed comments

def findTheLongestBalancedSubstring(s: str) -> int:
    # List to store (char, count) for each group of consecutive characters
    groups = []
    
    # Track the current character and its count
    current_char = s[0]
    count = 1
    
    # Iterate through the string starting from the second character
    for ch in s[1:]:
        if ch == current_char:
            # Increase the count if the character is the same as the current one
            count += 1
        else:
            # Append the current group and reset for the new character
            groups.append((current_char, count))
            current_char = ch
            count = 1
    # Append the final group
    groups.append((current_char, count))
    
    # Variable to track maximum balanced substring length
    max_length = 0
    
    # Examine adjacent groups: if the first is '0' and next is '1'
    for i in range(len(groups) - 1):
        char_current, count_current = groups[i]
        char_next, count_next = groups[i + 1]
        
        # Check if the group forms a valid balanced sequence: "0...0 1...1"
        if char_current == '0' and char_next == '1':
            # The maximum balanced substring from these two groups is twice the minimum count
            balanced_length = 2 * min(count_current, count_next)
            max_length = max(max_length, balanced_length)
    
    return max_length

# Example test cases
print(findTheLongestBalancedSubstring("01000111"))  # Expected output: 6
print(findTheLongestBalancedSubstring("00111"))     # Expected output: 4
print(findTheLongestBalancedSubstring("111"))       # Expected output: 0