# 2609. Find the Longest Balanced Substring of a Binary String

## Description

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

A substring of s is considered balanced if all 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 of s.

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

Example 1:

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


Example 2:

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


Example 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'

## Solutions

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.

The time complexity is $O(n^3)$, and the space complexity is $O(1)$. Where $n$ is the length of string $s$.

Solution 2: Enumeration optimization

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

Traverse the string $s$, for the current character $c$:

• If the current character is '0', we check if $one$ is greater than $0$, if so, we reset $zero$ and $one$ to $0$, and then add $1$ to $zero$.
• If the current character is '1', we add $1$ to $one$, and update the answer to $ans = max(ans, 2 \times min(one, zero))$.

After the traversal is complete, we can get the length of the longest balanced substring.

The time complexity is $O(n)$, and the space complexity is $O(1)$. Where $n$ is the length of string $s$.

• class Solution {
public int findTheLongestBalancedSubstring(String s) {
int n = s.length();
int ans = 0;
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
if (check(s, i, j)) {
ans = Math.max(ans, j - i + 1);
}
}
}
return ans;
}

private boolean check(String s, int i, int j) {
int cnt = 0;
for (int k = i; k <= j; ++k) {
if (s.charAt(k) == '1') {
++cnt;
} else if (cnt > 0) {
return false;
}
}
return cnt * 2 == j - i + 1;
}
}

• class Solution {
public:
int findTheLongestBalancedSubstring(string s) {
int n = s.size();
int ans = 0;
auto check = [&](int i, int j) -> bool {
int cnt = 0;
for (int k = i; k <= j; ++k) {
if (s[k] == '1') {
++cnt;
} else if (cnt) {
return false;
}
}
return cnt * 2 == j - i + 1;
};
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
if (check(i, j)) {
ans = max(ans, j - i + 1);
}
}
}
return ans;
}
};

• 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


• func findTheLongestBalancedSubstring(s string) (ans int) {
n := len(s)
check := func(i, j int) bool {
cnt := 0
for k := i; k <= j; k++ {
if s[k] == '1' {
cnt++
} else if cnt > 0 {
return false
}
}
return cnt*2 == j-i+1
}
for i := 0; i < n; i++ {
for j := i + 1; j < n; j++ {
if check(i, j) {
ans = max(ans, j-i+1)
}
}
}
return
}

• function findTheLongestBalancedSubstring(s: string): number {
const n = s.length;
let ans = 0;
const check = (i: number, j: number): boolean => {
let cnt = 0;
for (let k = i; k <= j; ++k) {
if (s[k] === '1') {
++cnt;
} else if (cnt > 0) {
return false;
}
}
return cnt * 2 === j - i + 1;
};
for (let i = 0; i < n; ++i) {
for (let j = i + 1; j < n; j += 2) {
if (check(i, j)) {
ans = Math.max(ans, j - i + 1);
}
}
}
return ans;
}


• impl Solution {
pub fn find_the_longest_balanced_substring(s: String) -> i32 {
let check = |i: usize, j: usize| -> bool {
let mut cnt = 0;

for k in i..=j {
if s.as_bytes()[k] == b'1' {
cnt += 1;
} else if cnt > 0 {
return false;
}
}

cnt * 2 == j - i + 1
};

let mut ans = 0;
let n = s.len();
for i in 0..n - 1 {
for j in (i + 1..n).rev() {
if j - i + 1 < ans {
break;
}

if check(i, j) {
ans = std::cmp::max(ans, j - i + 1);
break;
}
}
}

ans as i32
}
}