LeetCode 2609 - Find the Longest Balanced Substring of a Binary String

The problem gives us a binary string s, which means the string contains only the characters '0' and '1'. We need to find the length of the longest substring that is considered balanced. A substring is balanced when two conditions are satisfied: 1.

leetcodeeasystring

LeetCode Problem 2609

Difficulty: 🟢 Easy
Topics: String

Solution

Problem Understanding

The problem gives us a binary string s, which means the string contains only the characters '0' and '1'. We need to find the length of the longest substring that is considered balanced.

A substring is balanced when two conditions are satisfied:

  1. All zeroes appear before all ones.
  2. The number of zeroes equals the number of ones.

This means every valid balanced substring must have the structure:

000...111...

where the count of zeroes and ones is exactly the same.

For example:

  • "0011" is balanced because it contains two zeroes followed by two ones.
  • "000111" is balanced because it contains three zeroes followed by three ones.
  • "0101" is not balanced because the characters alternate instead of grouping all zeroes before ones.
  • "011" is not balanced because the counts are different.

The task is to return the maximum possible length among all balanced substrings. If no non-empty balanced substring exists, we return 0. The problem explicitly states that the empty substring is balanced, which guarantees that the answer is always at least 0.

The constraints are very small:

  • 1 <= s.length <= 50

Since the input size is tiny, even brute-force solutions are acceptable from a performance perspective. However, the goal is still to design a clean and efficient algorithm.

Several edge cases are important:

  • A string containing only '1' characters, such as "111", has no valid non-empty balanced substring.
  • A string containing only '0' characters also has no valid balanced substring because there are no ones to match the zeroes.
  • A string with multiple groups, such as "0001110011", requires checking transitions carefully because the best answer may appear in the middle.
  • Strings like "010101" contain many short valid substrings but no long ones.

The key observation is that every balanced substring must be formed around a transition from '0' to '1'.

Approaches

Brute Force Approach

The brute-force solution checks every possible substring of s.

For each substring, we verify whether:

  1. All zeroes come before all ones.
  2. The number of zeroes equals the number of ones.

To perform the validation, we can scan the substring character by character. We count zeroes and ones while also ensuring that once we encounter a '1', we never see another '0'.

If the substring satisfies all conditions, we update the maximum length.

This approach is correct because it explicitly evaluates every possible substring and directly tests the definition of a balanced substring. However, it is inefficient because there are many substrings to examine.

With a string of length n:

  • There are O(n²) substrings.
  • Validating each substring takes O(n) time.

This produces an overall complexity of O(n³).

Even though n <= 50 makes this acceptable, we can do much better.

Optimal Approach

The important observation is that every balanced substring consists of:

  • A consecutive block of zeroes
  • Followed immediately by a consecutive block of ones

For example:

000111

If we know:

  • the number of consecutive zeroes before a transition
  • the number of consecutive ones after the transition

then the largest balanced substring centered around that transition has length:

2 * min(zero_count, one_count)

Why does this work?

Suppose we have:

0000111

There are 4 zeroes and 3 ones. We can only match 3 pairs, so the longest balanced substring is:

000111

with length 6.

We can solve the problem in one pass by tracking consecutive groups of characters.

Approach Time Complexity Space Complexity Notes
Brute Force O(n³) O(1) Checks every substring and validates it directly
Optimal O(n) O(1) Counts consecutive zero and one groups

Algorithm Walkthrough

  1. Initialize three variables:
  • previous_zero_count
  • current_one_count
  • max_length

These variables help track the current groups of zeroes and ones. 2. Traverse the string from left to right. 3. When we encounter a group of zeroes, count how many consecutive zeroes appear. 4. After the zero group ends, count how many consecutive ones follow it immediately. 5. Once both groups are counted:

  • The largest balanced substring using these groups has length:
2 * min(zero_count, one_count)
  1. Update max_length if this balanced substring is larger than the current answer.
  2. Continue scanning the rest of the string until the traversal is complete.
  3. Return max_length.

Why it works

Every valid balanced substring must consist of consecutive zeroes followed by consecutive ones. Therefore, every balanced substring is fully determined by one adjacent pair of groups:

000...111...

The limiting factor is the smaller group because we need equal numbers of zeroes and ones. Taking:

2 * min(zero_count, one_count)

guarantees the largest possible balanced substring for that transition. Since the algorithm examines every such transition exactly once, it always finds the global maximum.

Python Solution

class Solution:
    def findTheLongestBalancedSubstring(self, s: str) -> int:
        n = len(s)
        max_length = 0
        i = 0

        while i < n:
            zero_count = 0
            one_count = 0

            while i < n and s[i] == '0':
                zero_count += 1
                i += 1

            while i < n and s[i] == '1':
                one_count += 1
                i += 1

            max_length = max(max_length, 2 * min(zero_count, one_count))

        return max_length

The implementation uses a single index i to traverse the string.

At each step, the algorithm first counts a consecutive group of zeroes. After that, it counts the consecutive group of ones immediately following those zeroes.

Once both counts are known, the algorithm computes the maximum balanced substring possible for that pair of groups. Since equal numbers of zeroes and ones are required, the smaller count determines how many matched pairs we can form.

The expression:

2 * min(zero_count, one_count)

gives the length of the largest balanced substring for the current segment.

The algorithm repeats this process until the entire string has been processed.

Go Solution

func findTheLongestBalancedSubstring(s string) int {
	n := len(s)
	maxLength := 0
	i := 0

	for i < n {
		zeroCount := 0
		oneCount := 0

		for i < n && s[i] == '0' {
			zeroCount++
			i++
		}

		for i < n && s[i] == '1' {
			oneCount++
			i++
		}

		currentLength := 2 * min(zeroCount, oneCount)

		if currentLength > maxLength {
			maxLength = currentLength
		}
	}

	return maxLength
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

The Go implementation follows the same logic as the Python version. Since Go does not provide a built-in integer minimum function for plain integers, we define a helper min function.

Strings in Go can be indexed directly using s[i] because the input contains only ASCII characters '0' and '1'. No additional Unicode handling is necessary.

The algorithm uses only integer variables and constant extra memory.

Worked Examples

Example 1

Input: s = "01000111"

We trace the algorithm step by step.

Step Current Index Zero Count One Count Balanced Length Max Length
Start first group 0 1 1 2 2
Start second group 2 3 3 6 6

Detailed walkthrough:

  • First segment:

  • "0" gives zero_count = 1

  • "1" gives one_count = 1

  • Balanced length = 2 * min(1,1) = 2

  • Second segment:

  • "000" gives zero_count = 3

  • "111" gives one_count = 3

  • Balanced length = 2 * min(3,3) = 6

Final answer:

6

Example 2

Input: s = "00111"
Step Current Index Zero Count One Count Balanced Length Max Length
First group 0 2 3 4 4

Detailed walkthrough:

  • Consecutive zeroes: "00" → zero_count = 2
  • Consecutive ones: "111" → one_count = 3
  • We can only match 2 pairs.

Balanced length:

2 * min(2,3) = 4

Final answer:

4

Example 3

Input: s = "111"
Step Current Index Zero Count One Count Balanced Length Max Length
Only group 0 0 3 0 0

There are no zeroes before the ones, so no valid non-empty balanced substring exists.

Final answer:

0

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each character is processed at most once
Space O(1) Only a few integer variables are used

The algorithm performs a single linear scan of the string. Each character belongs to exactly one zero-group count and one one-group count, so the total work is proportional to the string length.

No auxiliary data structures are required, which keeps the space usage constant.

Test Cases

solution = Solution()

assert solution.findTheLongestBalancedSubstring("01000111") == 6  # example with large balanced block
assert solution.findTheLongestBalancedSubstring("00111") == 4  # extra ones after matching
assert solution.findTheLongestBalancedSubstring("111") == 0  # no leading zeroes
assert solution.findTheLongestBalancedSubstring("000") == 0  # no ones
assert solution.findTheLongestBalancedSubstring("01") == 2  # smallest non-empty balanced substring
assert solution.findTheLongestBalancedSubstring("0011") == 4  # perfectly balanced
assert solution.findTheLongestBalancedSubstring("000111") == 6  # large balanced substring
assert solution.findTheLongestBalancedSubstring("0001111") == 6  # more ones than zeroes
assert solution.findTheLongestBalancedSubstring("00110011") == 4  # multiple balanced regions
assert solution.findTheLongestBalancedSubstring("010101") == 2  # many small valid substrings
assert solution.findTheLongestBalancedSubstring("100011") == 4  # balanced substring in middle
assert solution.findTheLongestBalancedSubstring("00001111") == 8  # entire string balanced
assert solution.findTheLongestBalancedSubstring("011110") == 2  # only one short balanced substring
assert solution.findTheLongestBalancedSubstring("101010") == 2  # alternating starting with one
assert solution.findTheLongestBalancedSubstring("0000011111") == 10  # equal large groups
Test Why
"01000111" Verifies longest substring appears later
"00111" Tests unequal group sizes
"111" No balanced substring exists
"000" Missing ones entirely
"01" Smallest valid balanced substring
"0011" Perfectly balanced small input
"000111" Entire string is balanced
"0001111" Extra trailing ones
"00110011" Multiple candidate regions
"010101" Many short valid substrings
"100011" Balanced substring not at start
"00001111" Large full-string balance
"011110" Valid substring surrounded by invalid chars
"101010" Alternating pattern starting with one
"0000011111" Larger equal groups

Edge Cases

One important edge case is a string containing only one type of character, such as "0000" or "1111". A naive implementation might incorrectly assume that any repeated pattern contributes to a balanced substring. However, balanced substrings require both zeroes and ones. The implementation handles this naturally because one of the counts becomes zero, making:

2 * min(zero_count, one_count)

equal to zero.

Another important case is when the counts of zeroes and ones are unequal, such as "0001111". The algorithm must correctly use only the smaller count because balanced substrings require equal numbers of both characters. The implementation handles this by taking the minimum of the two counts, producing:

2 * min(3,4) = 6

instead of incorrectly returning 7.

A third tricky case is alternating patterns such as "010101". It is easy to mistakenly combine multiple separate balanced regions into one larger answer. However, balanced substrings must contain all zeroes before all ones. The implementation processes one consecutive zero-group and one consecutive one-group at a time, preventing invalid combinations and correctly returning 2.

Another subtle edge case occurs when the balanced substring appears in the middle of the string, such as "100011". A naive implementation focused only on prefixes or suffixes could miss this. The linear scan examines every adjacent zero-group and one-group pair, ensuring that balanced substrings anywhere in the string are considered correctly.