---

0696. 计数二进制子串

• 标签：双指针、字符串
• 难度：简单

题目链接

• 0696. 计数二进制子串 - 力扣

题目大意

描述：

给定一个字符串 $s$。

要求：

统计并返回具有相同数量 $0$ 和 $1$ 的非空（连续）子字符串的数量，并且这些子字符串中的所有 $0$ 和所有 $1$ 都是成组连续的。

重复出现（不同位置）的子串也要统计它们出现的次数。

说明：

• $1 \le s.length \le 10^{5}$。
• $s[i]$ 为 '0' 或 '1'。

示例：

• 示例 1：

输入：s = "00110011"
输出：6
解释：6 个子串满足具有相同数量的连续 1 和 0 ："0011"、"01"、"1100"、"10"、"0011" 和 "01" 。
注意，一些重复出现的子串（不同位置）要统计它们出现的次数。
另外，"00110011" 不是有效的子串，因为所有的 0（还有 1 ）没有组合在一起。

• 示例 2：

输入：s = "10101"
输出：4
解释：有 4 个子串："10"、"01"、"10"、"01" ，具有相同数量的连续 1 和 0 。

解题思路

思路 1：双指针

思路 1：算法描述

这道题目要求统计具有相同数量 $0$ 和 $1$ 的非空连续子字符串的数量，并且这些子字符串中的所有 $0$ 和所有 $1$ 都是成组连续的。

我们可以使用双指针的方法，统计连续的 $0$ 和 $1$ 的个数。

具体步骤如下：

1. 初始化 $prev = 0$（前一组字符的个数）和 $curr = 1$（当前组字符的个数）。
2. 初始化结果 $ans = 0$。
3. 从左到右遍历字符串 $s$，对于每个位置 $i$（从 $1$ 开始）：
   • 如果 $s[i] = s[i - 1]$，说明当前字符与前一个字符相同，将 $curr$ 加 $1$。
   • 否则，说明遇到了新的一组字符，此时可以形成的子字符串数量为 $\min(prev, curr)$，将其加到 $ans$ 中，然后更新 $prev = curr$，$curr = 1$。
4. 遍历结束后，还需要加上最后一组字符可以形成的子字符串数量 $\min(prev, curr)$。
5. 返回 $ans$。

思路 1：代码

class Solution:
    def countBinarySubstrings(self, s: str) -> int:
        prev = 0  # 前一组字符的个数
        curr = 1  # 当前组字符的个数
        ans = 0   # 结果
        
        # 遍历字符串
        for i in range(1, len(s)):
            if s[i] == s[i - 1]:
                # 当前字符与前一个字符相同
                curr += 1
            else:
                # 遇到新的一组字符
                ans += min(prev, curr)
                prev = curr
                curr = 1
        
        # 加上最后一组字符可以形成的子字符串数量
        ans += min(prev, curr)
        
        return ans

思路 1：复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 是字符串的长度。只需要遍历一次字符串。
• 空间复杂度：$O(1)$。只使用了常数级别的额外空间。