How to Find the Longest Balanced Substring in a Binary String (LeetCode 2609)

Problem Description

Given a binary string s consisting only of characters ‘0’ and ‘1’, a substring is called balanced if all ‘0’s appear before any ‘1’ and the number of ‘0’s equals the number of ‘1’s. The empty substring is also considered balanced. Return the length of the longest balanced substring in s.

Examples

Input s = "01000111" → Output 6. The longest balanced substring is "000111".

Input s = "00111" → Output 4. The longest balanced substring is "0011".

Input s = "111" → Output 0. No non‑empty balanced substring exists.

Approach

The balanced substring must have the form 0…01…1 where the count of leading zeros equals the count of trailing ones. Perform a linear scan with an index idx. For each segment, count the length a of consecutive zeros and the length b of the following consecutive ones. The candidate balanced length is 2 * min(a, b), which updates the answer. Continue scanning from the end of the processed segment.

Complexity Analysis

Time complexity: O(n), where n is the length of s.

Space complexity: O(1).

Reference Implementations

class Solution {
    public int findTheLongestBalancedSubstring(String s) {
        int n = s.length(), idx = 0, ans = 0;
        while (idx < n) {
            int a = 0, b = 0;
            while (idx < n && s.charAt(idx) == '0' && ++a >= 0) idx++;
            while (idx < n && s.charAt(idx) == '1' && ++b >= 0) idx++;
            ans = Math.max(ans, Math.min(a, b) * 2);
        }
        return ans;
    }
}

class Solution {
    int findTheLongestBalancedSubstring(string s) {
        int n = s.size(), idx = 0, ans = 0;
        while (idx < n) {
            int a = 0, b = 0;
            while (idx < n && s[idx] == '0' && ++a >= 0) idx++;
            while (idx < n && s[idx] == '1' && ++b >= 0) idx++;
            ans = max(ans, min(a, b) * 2);
        }
        return ans;
    }
};

class Solution:
    def findTheLongestBalancedSubstring(self, s: str) -> int:
        n, idx, ans = len(s), 0, 0
        while idx < n:
            a = b = 0
            while idx < n and s[idx] == '0':
                a, idx = a + 1, idx + 1
            while idx < n and s[idx] == '1':
                b, idx = b + 1, idx + 1
            ans = max(ans, min(a, b) * 2)
        return ans

function findTheLongestBalancedSubstring(s: string): number {
    let n = s.length, idx = 0, ans = 0;
    while (idx < n) {
        let a = 0, b = 0;
        while (idx < n && s[idx] == '0' && ++a >= 0) idx++;
        while (idx < n && s[idx] == '1' && ++b >= 0) idx++;
        ans = Math.max(ans, Math.min(a, b) * 2);
    }
    return ans;
}