Problem Description

You are given a binary string s that contains only '0' and '1' characters.

A substring is considered balanced if it meets two conditions:

1. All zeros ('0') appear before all ones ('1') in the substring
2. The number of zeros equals the number of ones

For example:

• "0011" is balanced (2 zeros, then 2 ones)
• "000111" is balanced (3 zeros, then 3 ones)
• "0101" is NOT balanced (zeros and ones are mixed)
• "001" is NOT balanced (different counts of zeros and ones)
• "" (empty string) is considered balanced

Your task is to find the length of the longest balanced substring within the given string s.

The solution uses a brute force approach with time complexity O(n³). It checks every possible substring s[i..j] by:

1. Enumeration: Using two nested loops to generate all possible substrings
2. Validation: The check function verifies if a substring is balanced by:
   • Counting the number of '1's
   • Ensuring no '0' appears after the first '1' is encountered
   • Confirming the total length equals twice the count of '1's (meaning equal zeros and ones)
3. Tracking: Maintaining the maximum length found among all valid balanced substrings

The algorithm returns the length of the longest balanced substring found, or 0 if no balanced substring exists.

Intuition

When we look at what makes a substring balanced, we notice it must have a very specific structure: consecutive zeros followed by consecutive ones, with equal counts. This means a balanced substring always looks like "00...0011...11".

Since we need to find the longest such substring, the natural starting point is to consider every possible substring and check if it's balanced. Why does this make sense? Because the balanced substring could start and end at any position in the string.

The key insight for checking if a substring is balanced comes from understanding what would make it unbalanced:

1. If we see a '0' after we've already seen a '1', the substring is immediately invalid
2. If the counts don't match, it's invalid

This leads us to the checking strategy: as we scan through a substring, we can count the '1's we encounter. If we ever see a '0' after we've started counting '1's (when cnt > 0), we know the substring violates the "all zeros before ones" rule. At the end, if our count of '1's times 2 equals the substring length, we know we have equal zeros and ones.

The brute force approach emerges naturally because:

• We don't know where the longest balanced substring starts or ends
• Each substring needs individual validation since there's no obvious pattern to predict which ones are balanced
• The constraints allow us to check all O(n²) substrings without timing out

While more efficient solutions exist (like tracking consecutive runs of '0's and '1's), the brute force method is the most straightforward way to guarantee we don't miss any potential balanced substring.

Solution Approach

The implementation uses a brute force approach with nested loops to examine all possible substrings.

Main Algorithm Structure:

1. Outer enumeration loop: The solution uses two nested loops to generate all possible substrings:

   • The outer loop for i in range(n) sets the starting position
   • The inner loop for j in range(i + 1, n) sets the ending position
   • This generates all substrings s[i..j] where i < j

2. Validation function check(i, j): For each substring, we verify if it's balanced:

   • Initialize a counter cnt = 0 to track the number of '1's
   • Iterate through the substring from position i to j
   • If we encounter a '1', increment the counter
   • If we encounter a '0' AND we've already seen at least one '1' (when cnt > 0), immediately return False as this violates the "all zeros before ones" rule
   • After scanning the entire substring, check if cnt * 2 == (j - i + 1), which ensures equal numbers of zeros and ones

3. Answer tracking:

   • Initialize ans = 0 to store the maximum length found
   • Whenever we find a valid balanced substring, update ans = max(ans, j - i + 1)
   • The length is calculated as j - i + 1 since we're using inclusive indices

Key Implementation Details:

• The check function cleverly combines two validations in one pass: it ensures zeros come before ones while simultaneously counting ones
• The expression elif cnt: is a shorthand for elif cnt > 0:, checking if we've started counting ones
• The final validation cnt * 2 == (j - i + 1) works because if there are cnt ones and the total length is j - i + 1, then there must be (j - i + 1) - cnt zeros. For balance, we need cnt == (j - i + 1) - cnt, which simplifies to cnt * 2 == (j - i + 1)

Time Complexity: O(n³) - Two nested loops generate O(n²) substrings, and each validation takes O(n) time.

Space Complexity: O(1) - Only using a few variables for tracking, no additional data structures needed.

Example Walkthrough

Let's walk through the solution with the string s = "001011".

Step 1: Initialize

• n = 6 (length of string)
• ans = 0 (to track maximum balanced substring length)

Step 2: Enumerate all substrings

We'll check each substring systematically:

i = 0 (starting from index 0):

• j = 1: Check "00" → Not balanced (2 zeros, 0 ones)
• j = 2: Check "001" → Not balanced (2 zeros, 1 one)
• j = 3: Check "0010" → Not balanced (has '0' after '1')
• j = 4: Check "00101" → Not balanced (has '0' after '1')
• j = 5: Check "001011" → Not balanced (has '0' after '1')

i = 1 (starting from index 1):

• j = 2: Check "01" → Balanced! (1 zero, 1 one, zeros before ones)
  • Update ans = 2
• j = 3: Check "010" → Not balanced (has '0' after '1')
• j = 4: Check "0101" → Not balanced (has '0' after '1')
• j = 5: Check "01011" → Not balanced (has '0' after '1')

i = 2 (starting from index 2):

• j = 3: Check "10" → Not balanced (1 one, 1 zero, but zero comes after one)
• j = 4: Check "101" → Not balanced (has '0' after '1')
• j = 5: Check "1011" → Not balanced (has '0' after '1')

i = 3 (starting from index 3):

• j = 4: Check "01" → Balanced! (1 zero, 1 one, zeros before ones)
  • ans remains 2 (not larger than current max)
• j = 5: Check "011" → Not balanced (1 zero, 2 ones)

i = 4 (starting from index 4):

• j = 5: Check "11" → Not balanced (0 zeros, 2 ones)

Step 3: Return result The longest balanced substring has length 2 (either "01" at indices [1,2] or [3,4]).

How the check function works for "01" (indices 1 to 2):

1. Start with cnt = 0
2. At index 1: see '0', cnt is still 0, continue
3. At index 2: see '1', increment cnt to 1
4. Final check: cnt * 2 = 1 * 2 = 2, substring length = 2 - 1 + 1 = 2
5. Since 2 == 2, return True (balanced!)

How the check function works for "010" (indices 1 to 3):

1. Start with cnt = 0
2. At index 1: see '0', cnt is still 0, continue
3. At index 2: see '1', increment cnt to 1
4. At index 3: see '0', but cnt > 0 (we've seen a '1'), return False immediately

Solution Implementation

Time and Space Complexity

The time complexity of this code is O(n³), where n is the length of string s.

This is because:

• The outer loop starting at line 13 iterates through all possible starting positions i, which runs n times
• The inner loop at line 14 iterates through all possible ending positions j from i+1 to n-1, which runs up to n-1 times in the worst case
• For each pair (i, j), the check function is called, which iterates from i to j (line 5), taking up to n operations in the worst case
• Therefore, the total time complexity is O(n) × O(n) × O(n) = O(n³)

The space complexity is O(1) as the algorithm only uses a constant amount of extra space:

• The check function uses a single integer variable cnt to count occurrences
• The main function uses variables n and ans to store the length and result
• No additional data structures that grow with input size are used

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Off-by-One Error in Substring Length Calculation

A common mistake is incorrectly calculating the substring length or using the wrong loop boundaries. Many developers accidentally write:

Incorrect:

for end in range(start + 1, string_length):
    if is_balanced_substring(start, end):
        current_length = end - start  # Wrong! Missing +1

Correct:

for end in range(start + 1, string_length):
    if is_balanced_substring(start, end):
        current_length = end - start + 1  # Correct: inclusive indices

2. Incorrect Loop Range Leading to Missing Substrings

Another pitfall is using range(start, string_length) for the end index, which would miss single-character positions and create confusion with inclusive/exclusive boundaries:

Incorrect:

for start in range(string_length):
    for end in range(start, string_length):  # Wrong! Includes start==end
        if is_balanced_substring(start, end):
            # This would check single characters and empty substrings

Correct:

for start in range(string_length):
    for end in range(start + 1, string_length):  # Ensures end > start
        if is_balanced_substring(start, end):
            # Properly checks substrings of length 2 or more

3. Forgetting Edge Cases for Empty or Odd-Length Substrings

Since balanced substrings must have equal zeros and ones, they must have even length. Checking odd-length substrings wastes computation:

Optimized Solution:

for start in range(string_length):
    # Start from start+1 and increment by 2 for even-length substrings only
    for end in range(start + 1, string_length, 2):
        if is_balanced_substring(start, end):
            current_length = end - start + 1
            max_balanced_length = max(max_balanced_length, current_length)

4. Inefficient Validation Logic

Some implementations might check the balanced property inefficiently by first counting all zeros and ones, then checking their positions:

Inefficient:

def is_balanced_substring(start, end):
    substring = s[start:end+1]
    zeros = substring.count('0')
    ones = substring.count('1')
    if zeros != ones:
        return False
    # Then check if all zeros come before ones
    first_one_idx = substring.find('1')
    if first_one_idx != -1:
        return '0' not in substring[first_one_idx:]
    return True

The original solution's approach is better as it combines both checks in a single pass, immediately returning False when finding a '0' after a '1'.