题目描述
给你一个仅由 0 和 1 组成的二进制字符串 s 。
如果子字符串中 所有的 0 都在 1 之前 且其中 0 的数量等于 1 的数量，则认为 s 的这个子字符串是平衡子字符串。请注意，空子字符串也视作平衡子字符串。
返回 s 中最长的平衡子字符串长度。
子字符串是字符串中的一个连续字符序列。
示例 1：
输入：s = "01000111"
输出：6
解释：最长的平衡子字符串是 "000111" ，长度为 6 。
示例 2：
输入：s = "00111"
输出：4
解释：最长的平衡子字符串是 "0011" ，长度为 4 。
示例 3：
输入：s = "111"
输出：0
解释：除了空子字符串之外不存在其他平衡子字符串，所以答案为 0 。
提示：
1 <= s.length <= 50'0' <= s[i] <= '1'
解法
方法一：暴力枚举
注意到数据范围很小，因此，我们可以枚举所有的子串 $s[i..j]$，检查其是否为平衡子串，如果是，则更新答案。
时间复杂度 $O(n^3)$，空间复杂度 $O(1)$。其中 $n$ 为字符串 $s$ 的长度。
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
}
}
|
方法二：枚举优化
我们用变量 $zero$ 和 $one$ 分别记录当前连续的 $0$ 和 $1$ 的个数。
遍历字符串 $s$，对于当前字符 $c$：
- 如果当前字符为
'0'，我们判断此时 $one$ 是否大于 $0$，是则将 $zero$ 和 $one$ 重置为 $0$，接下来将 $zero$ 加 $1$。
- 如果当前字符为
'1'，则将 $one$ 加 $1$，并更新答案为 $ans = \max(ans, 2 \times \min(one, zero))$。
遍历结束后，即可得到最长的平衡子串的长度。
时间复杂度 $O(n)$，空间复杂度 $O(1)$。其中 $n$ 为字符串 $s$ 的长度。
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
}
}
|