LeetCode 2609. 最长平衡子字符串

【LetMeFly】2609.最长平衡子字符串

力扣题目链接：https://leetcode.cn/problems/find-the-longest-balanced-substring-of-a-binary-string/

给你一个仅由 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'

方法一：字符串处理

“平衡字符串”的前提是数个0后面有数个1。因此，我们可以使用一个变量index来存储当前处理到的字符，每次遍历完所有相连的0后遍历所有相邻的1，其中0和1的最小值的二倍即为当前“平衡子字符串”的长度。

index = 0
while index < len(s):
    cnt0 = 0
    while index < len(s) and s[index] == '0':  # 遍历完所有的0
        cnt0++, index++
    while index < len(s) and s[index] == '1':  # 遍历完所有的0
        cnt1++, index++
	thisLength = 2 * min(cnt0, cnt1)
	# 更新answer
1
2
3
4
5
6
7
8
9

• 时间复杂度$O(len(s))$
• 空间复杂度$O(1)$

AC代码

C++

class Solution {
public:
    int findTheLongestBalancedSubstring(string s) {
        int ans = 0, index = 0;
        while (index < s.size()) {
            int cnt0 = 0, cnt1 = 0;
            while (index < s.size() && s[index] == '0') {
                cnt0++, index++;
            }
            while (index < s.size() && s[index] == '1') {
                cnt1++, index++;
            }
            ans = max(ans, 2 * min(cnt0, cnt1));
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

Python

class Solution:
    def findTheLongestBalancedSubstring(self, s: str) -> int:
        ans, index = 0, 0
        while index < len(s):
            cnt0, cnt1 = 0, 0
            while index < len(s) and s[index] == '0':
                cnt0, index = cnt0 + 1, index + 1
            while index < len(s) and s[index] == '1':
                cnt1, index = cnt1 + 1, index + 1
            ans = max(ans, 2 * min(cnt0, cnt1))
        return ans
1
2
3
4
5
6
7
8
9
10
11

同步发文于CSDN，原创不易，转载经作者同意后请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/134296484