#2609

Easy

auto_awesomeString-driven solution strategy

LeetCode Problem Workspace

Find the Longest Balanced Substring of a Binary String

Find the longest balanced substring of a binary string where zeroes precede ones and counts of each are equal.

Problem Statement

You are given a binary string s consisting of zeroes and ones. Your task is to return the length of the longest balanced substring in s. A balanced substring has equal numbers of zeroes and ones, with all zeroes occurring before any ones.

For example, the substring 000111 is balanced, but 001101 is not. If no balanced substring exists, the empty substring is considered balanced and the answer is 0.

Examples

Example 1

Input: s = "01000111"

Output: 6

The longest balanced substring is "000111", which has length 6.

Example 2

Input: s = "00111"

Output: 4

The longest balanced substring is "0011", which has length 4.

Example 3

Input: s = "111"

Output: 0

There is no balanced substring except the empty substring, so the answer is 0.

Constraints

1 <= s.length <= 50
'0' <= s[i] <= '1'

Solution Approach

Iterate and Check Every Substring

One approach is to iterate through every possible substring of s, checking if it’s balanced. This involves comparing counts of zeroes and ones and ensuring zeroes come first.

Use Prefix Sum to Optimize

Instead of checking every substring, you can use a prefix sum to track the balance of zeroes and ones as you traverse the string. This helps to quickly identify balanced substrings.

Sliding Window Technique

A sliding window approach can also be effective. By expanding and shrinking the window while maintaining the balance, you can efficiently find the longest balanced substring.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on the approach: iterating through all substrings results in O(n^2) time complexity, while using a prefix sum can optimize it to O(n). The space complexity for the prefix sum approach is O(n), while the sliding window approach typically uses O(1) additional space.

What Interviewers Usually Probe

The candidate is familiar with string manipulation and optimization strategies.
The candidate can implement efficient substring checks with prefix sum or sliding window.
The candidate can distinguish between brute force and optimized approaches.

Common Pitfalls or Variants

Common pitfalls

Incorrectly counting zeroes and ones in a substring.
Overlooking cases where no balanced substring exists.
Not considering the empty substring as balanced in the edge cases.

Follow-up variants

Handling edge cases with no balanced substrings.
Optimizing with different window sizes.
Applying different balancing rules such as alternating zeroes and ones.

FAQ

How can I solve the problem of finding the longest balanced substring of a binary string?

You can use a string-driven approach, either by iterating through all substrings or using a more optimized method like prefix sums or sliding window.

What is the most efficient way to solve the longest balanced substring problem?

Using a prefix sum or sliding window technique optimizes the process, reducing time complexity to O(n).

What does 'balanced substring' mean in this problem?

A balanced substring has equal numbers of zeroes and ones, with all zeroes preceding the ones.

Can the empty substring be considered balanced?

Yes, the empty substring is considered balanced, meaning the answer is 0 when no other balanced substring is found.

What are common pitfalls in solving the longest balanced substring problem?

Common mistakes include miscounting zeroes and ones or failing to handle edge cases with no balanced substrings.

terminal

Solution

Solution 1: Brute force

Since the range of $n$ is small, we can enumerate all substrings $s[i..j]$ to check if it is a balanced string. If so, update the answer.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

class Solution:
    def findTheLongestBalancedSubstring(self, s: str) -> int:
        def check(i, j):
            cnt = 0
            for k in range(i, j + 1):
                if s[k] == '1':
                    cnt += 1
                elif cnt:
                    return False
            return cnt * 2 == (j - i + 1)

        n = len(s)
        ans = 0
        for i in range(n):
            for j in range(i + 1, n):
                if check(i, j):
                    ans = max(ans, j - i + 1)
        return ans

Solution 2: Enumeration optimization

We use variables $zero$ and $one$ to record the number of continuous $0$ and $1$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

class Solution:
    def findTheLongestBalancedSubstring(self, s: str) -> int:
        def check(i, j):
            cnt = 0
            for k in range(i, j + 1):
                if s[k] == '1':
                    cnt += 1
                elif cnt:
                    return False
            return cnt * 2 == (j - i + 1)

        n = len(s)
        ans = 0
        for i in range(n):
            for j in range(i + 1, n):
                if check(i, j):
                    ans = max(ans, j - i + 1)
        return ans

Continue Practicing

#2606 find the substring with maximum cost #2586 count the number of vowel strings in range #2575 find the divisibility array of a string