Problem

You are given a binary string s consisting only of zeroes and ones.

A substring of s is considered balanced ifall zeroes are before ones and the number of zeroes is equal to the number of ones inside the substring. Notice that the empty substring is considered a balanced substring.

Return the length of the longest balanced substring ofs.

A substring is a contiguous sequence of characters within a string.

Examples

Example 1

1
2
3

Input: s = "01000111"
Output: 6
Explanation: The longest balanced substring is "000111", which has length 6.

Example 2

1
2
3

Input: s = "00111"
Output: 4
Explanation: The longest balanced substring is "0011", which has length 4.

Example 3

1
2
3

Input: s = "111"
Output: 0
Explanation: There is no balanced substring except the empty substring, so the answer is 0.

Constraints

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

Solution

Method 1 – Group Counting and Greedy Matching

Intuition

A balanced substring must have all 0s before all 1s and equal numbers of each. By counting consecutive groups of 0s and 1s, the maximum balanced substring at each transition is twice the minimum of the current 0-group and 1-group.

Approach

  1. Initialize counters for consecutive 0s (cnt0) and 1s (cnt1), and a variable for the answer.
  2. Traverse the string:
    • If the current character is ‘0’, increment cnt0 (reset cnt1 if previous was ‘1’).
    • If the current character is ‘1’, increment cnt1.
    • When switching from ‘0’ to ‘1’, update the answer as max(ans, 2 * min(cnt0, cnt1)).
    • When switching from ‘1’ to ‘0’, reset cnt0 to 1 and cnt1 to 0.
  3. After the loop, check for the last group and update the answer.
  4. Return the answer.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
public:
    int findTheLongestBalancedSubstring(string s) {
        int ans = 0, cnt0 = 0, cnt1 = 0;
        for (char c : s) {
            if (c == '0') {
                if (cnt1 > 0) cnt0 = 0;
                cnt0++;
                cnt1 = 0;
            } else {
                cnt1++;
                ans = max(ans, 2 * min(cnt0, cnt1));
            }
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

func findTheLongestBalancedSubstring(s string) int {
    ans, cnt0, cnt1 := 0, 0, 0
    for _, c := range s {
        if c == '0' {
            if cnt1 > 0 { cnt0 = 0 }
            cnt0++
            cnt1 = 0
        } else {
            cnt1++
            if 2*min(cnt0, cnt1) > ans {
                ans = 2 * min(cnt0, cnt1)
            }
        }
    }
    return ans
}
func min(a, b int) int { if a < b { return a }; return b }
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    public int findTheLongestBalancedSubstring(String s) {
        int ans = 0, cnt0 = 0, cnt1 = 0;
        for (char c : s.toCharArray()) {
            if (c == '0') {
                if (cnt1 > 0) cnt0 = 0;
                cnt0++;
                cnt1 = 0;
            } else {
                cnt1++;
                ans = Math.max(ans, 2 * Math.min(cnt0, cnt1));
            }
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    fun findTheLongestBalancedSubstring(s: String): Int {
        var ans = 0; var cnt0 = 0; var cnt1 = 0
        for (c in s) {
            if (c == '0') {
                if (cnt1 > 0) cnt0 = 0
                cnt0++
                cnt1 = 0
            } else {
                cnt1++
                ans = maxOf(ans, 2 * minOf(cnt0, cnt1))
            }
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

def find_the_longest_balanced_substring(s: str) -> int:
    ans = cnt0 = cnt1 = 0
    for c in s:
        if c == '0':
            if cnt1 > 0:
                cnt0 = 0
            cnt0 += 1
            cnt1 = 0
        else:
            cnt1 += 1
            ans = max(ans, 2 * min(cnt0, cnt1))
    return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

impl Solution {
    pub fn find_the_longest_balanced_substring(s: String) -> i32 {
        let (mut ans, mut cnt0, mut cnt1) = (0, 0, 0);
        for c in s.chars() {
            if c == '0' {
                if cnt1 > 0 { cnt0 = 0; }
                cnt0 += 1;
                cnt1 = 0;
            } else {
                cnt1 += 1;
                ans = ans.max(2 * cnt0.min(cnt1));
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    findTheLongestBalancedSubstring(s: string): number {
        let ans = 0, cnt0 = 0, cnt1 = 0;
        for (const c of s) {
            if (c === '0') {
                if (cnt1 > 0) cnt0 = 0;
                cnt0++;
                cnt1 = 0;
            } else {
                cnt1++;
                ans = Math.max(ans, 2 * Math.min(cnt0, cnt1));
            }
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the length of s. We scan the string once.
  • 🧺 Space complexity: O(1), only counters are used.