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$.
Python3 Java C++ Go TypeScript Rust
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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26 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 ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26 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 ;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 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
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23 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 ;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34 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
}
}
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$.
Python3 Java C++ Go TypeScript Rust
1
2
3
4
5
6
7
8
9
10
11
12 class Solution :
def findTheLongestBalancedSubstring ( self , s : str ) -> int :
ans = zero = one = 0
for c in s :
if c == '0' :
if one :
zero = one = 0
zero += 1
else :
one += 1
ans = max ( ans , 2 * min ( one , zero ))
return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 class Solution {
public int findTheLongestBalancedSubstring ( String s ) {
int zero = 0 , one = 0 ;
int ans = 0 , n = s . length ();
for ( int i = 0 ; i < n ; ++ i ) {
if ( s . charAt ( i ) == '0' ) {
if ( one > 0 ) {
zero = 0 ;
one = 0 ;
}
++ zero ;
} else {
ans = Math . max ( ans , 2 * Math . min ( zero , ++ one ));
}
}
return ans ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 class Solution {
public :
int findTheLongestBalancedSubstring ( string s ) {
int zero = 0 , one = 0 ;
int ans = 0 ;
for ( char & c : s ) {
if ( c == '0' ) {
if ( one > 0 ) {
zero = 0 ;
one = 0 ;
}
++ zero ;
} else {
ans = max ( ans , 2 * min ( zero , ++ one ));
}
}
return ans ;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 func findTheLongestBalancedSubstring ( s string ) ( ans int ) {
zero , one := 0 , 0
for _ , c := range s {
if c == '0' {
if one > 0 {
zero , one = 0 , 0
}
zero ++
} else {
one ++
ans = max ( ans , 2 * min ( zero , one ))
}
}
return
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 function findTheLongestBalancedSubstring ( s : string ) : number {
let zero = 0 ;
let one = 0 ;
let ans = 0 ;
for ( const c of s ) {
if ( c === '0' ) {
if ( one > 0 ) {
zero = 0 ;
one = 0 ;
}
++ zero ;
} else {
ans = Math . max ( ans , 2 * Math . min ( zero , ++ one ));
}
}
return ans ;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 impl Solution {
pub fn find_the_longest_balanced_substring ( s : String ) -> i32 {
let mut zero = 0 ;
let mut one = 0 ;
let mut ans = 0 ;
for & c in s . as_bytes (). iter () {
if c == b'0' {
if one > 0 {
zero = 0 ;
one = 0 ;
}
zero += 1 ;
} else {
one += 1 ;
ans = std :: cmp :: max ( ans , std :: cmp :: min ( zero , one ) * 2 );
}
}
ans
}
}
GitHub