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'

本题视频讲解

见【周赛 339】 。

思路

记录上一段连续相同字符个数 pre，以及当前连续相同字符个数 cur。

如果当前字符是 1，那么上一段的字符是 0，这两段可以组成一个 01 串，由于 0 和 1 的个数需要相等，那么当前这个 01 串的最大长度就是

2\cdot \min(\textit{pre}, \textit{cur})

取所有长度的最大值，即为答案。更新答案的时候，可以在当前字符是 1，且下一个字符是 0 的位置上更新（或者 1 在最末尾的时候）。

[sol1-Python3]

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

[sol1-Java]

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;
    }
}

[sol1-C++]

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]) {
                if (s[i] == '1')
                    ans = max(ans, min(pre, cur) * 2);
                pre = cur;
                cur = 0;
            }
        }
        return ans;
    }
};

[sol1-Go]

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 }

复杂度分析

• 时间复杂度：O(n)，其中 n 为 s 的长度。
• 空间复杂度：O(1)。仅用到若干额外变量。