class Solution {
public:
int findTheLongestBalancedSubstring(string s) {
}
};
2609. 最长平衡子字符串
给你一个仅由 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'原站题解
cpp 解法, 执行用时: 0 ms, 内存消耗: 6.5 MB, 提交时间: 2023-11-08 22:39:01
class Solution {
public:
int findTheLongestBalancedSubstring(string s) {
int ans = 0, pre = 0, cur = 0, n = s.length();
for (int i = 0; i < n; i++) {
cur++;
if (i == s.length() - 1 || s[i] != s[i + 1]) { // i 是连续相同段的末尾
if (s[i] == '1') {
ans = max(ans, min(pre, cur) * 2);
}
pre = cur;
cur = 0;
}
}
return ans;
}
};
javascript 解法, 执行用时: 96 ms, 内存消耗: 44.8 MB, 提交时间: 2023-11-08 22:38:26
/**
* @param {string} s
* @return {number}
*/
var findTheLongestBalancedSubstring = function(s) {
let ans = 0, pre = 0, cur = 0;
for (let i = 0; i < s.length; i++) {
cur++;
if (i === s.length - 1 || s[i] !== s[i + 1]) { // i 是连续相同段的末尾
if (s[i] === '1') {
ans = Math.max(ans, Math.min(pre, cur) * 2);
}
pre = cur;
cur = 0;
}
}
return ans;
};
golang 解法, 执行用时: 0 ms, 内存消耗: 2.2 MB, 提交时间: 2023-04-10 09:50:55
func findTheLongestBalancedSubstring(s string) (ans int) {
pre, cur := 0, 0
for i, c := range s {
cur++
if i == len(s)-1 || byte(c) != s[i+1] {
if c == '1' {
ans = max(ans, min(pre, cur)*2)
}
pre = cur
cur = 0
}
}
return
}
func min(a, b int) int { if a > b { return b }; return a }
func max(a, b int) int { if a < b { return b }; return a }
java 解法, 执行用时: 1 ms, 内存消耗: 41.5 MB, 提交时间: 2023-04-10 09:50:41
class Solution {
public int findTheLongestBalancedSubstring(String S) {
var s = S.toCharArray();
int ans = 0, pre = 0, cur = 0, n = s.length;
for (int i = 0; i < n; ++i) {
++cur;
if (i == s.length - 1 || s[i] != s[i + 1]) {
if (s[i] == '1')
ans = Math.max(ans, Math.min(pre, cur) * 2);
pre = cur;
cur = 0;
}
}
return ans;
}
}
python3 解法, 执行用时: 48 ms, 内存消耗: 14.8 MB, 提交时间: 2023-04-10 09:50:27
'''
记录上一段连续相同字符个数 pre，以及当前连续相同字符个数 cur
'''
class Solution:
def findTheLongestBalancedSubstring(self, s: str) -> int:
ans = pre = cur = 0
for i, c in enumerate(s):
cur += 1
if i == len(s) - 1 or c != s[i + 1]:
if c == '1':
ans = max(ans, min(pre, cur) * 2)
pre = cur
cur = 0
return ans