题目描述
给你一个仅由 0
和 1
组成的二进制字符串 s
。
如果子字符串中 所有的 0
都在 1
之前 且其中 0
的数量等于 1
的数量,则认为 s
的这个子字符串是平衡子字符串。请注意,空子字符串也视作平衡子字符串。
返回 s
中最长的平衡子字符串长度。
子字符串是字符串中的一个连续字符序列。
样例
输入:s = "01000111"
输出:6
解释:最长的平衡子字符串是 "000111",长度为 6。
输入:s = "00111"
输出:4
解释:最长的平衡子字符串是 "0011",长度为 4。
输入:s = "111"
输出:0
解释:除了空子字符串之外不存在其他平衡子字符串,所以答案为 0。
限制
1 <= s.length <= 50
'0' <= s[i] <= '1'
算法
(思维题) $O(n)$
- 定义两个变量 $zero$ 和 $one$,分别表示在连续的 $1$ 之前连续的 $0$ 的数量,以及当前连续的 $1$ 的数量。
- 初始时,两个变量的值都是 $0$,遍历数组。
- 如果当前位置是 $1$,则 $one$ 累加 $1$。否则,如果存在上一个位置,且上一个位置是 $1$,则说明一个区间已经结束了,用 $2\min(zero, one)$ 更新答案,然后重置 $zero$ 和 $one$。
- 最终,遍历结束后还需要与 $2\min(zero, one)$ 取最大值作为最终答案。
时间复杂度
- 遍历数组一次,故时间复杂度为 $O(n)$。
空间复杂度
- 仅需要常数的额外空间。
C++ 代码
class Solution {
public:
int findTheLongestBalancedSubstring(string s) {
const int n = s.size();
int ans = 0, zero = 0, one = 0;
for (int i = 0; i < n; i++) {
if (s[i] == '1') {
one++;
continue;
}
if (i > 0 && s[i - 1] == '1') {
ans = max(ans, 2 * min(zero, one));
one = 0;
zero = 0;
}
zero++;
}
return max(ans, 2 * min(one, zero));
}
};