Easy

题目描述

给定一个二进制字符串 s，返回具有相同数量的 0 和 1 的非空子串的数量，并且这些子串中的所有 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 <= s.length <= 10^5
  • s[i] 要么是 '0'，要么是 '1'

提示：

  • 在 “000111” 中存在多少个有效的二进制子串，在 “11100” 中又有多少个？那么 “00011100” 呢？

解题思路

解题思路

这个问题的核心是找到满足条件的子串：有相同数量的0和1，且所有0和1都分别连续分组。

方法一：按组统计（推荐） 观察发现，符合条件的子串一定是由连续的0组和连续的1组组成，且这两个组的长度决定了能形成多少个有效子串。

算法步骤：

  1. 首先统计每个连续字符组的长度，存储在数组中
  2. 对于相邻的两个组，能形成的有效子串数量等于两组长度的最小值
  3. 例如"000111"有两组：长度3的0组和长度3的1组，可以形成min(3,3)=3个子串：“01”、“0011”、“000111”

方法二：双指针优化 我们可以进一步优化，不需要额外的数组存储所有组的长度，只需要记录前一组和当前组的长度即可。

这种方法的时间复杂度是O(n)，空间复杂度是O(1)，非常高效。

通过这种分组的思想，我们将复杂的子串匹配问题转换为简单的计数问题，大大简化了解决方案。

代码实现

class Solution {
public:
    int countBinarySubstrings(string s) {
        int result = 0;
        int prevGroup = 0, currGroup = 1;
        
        for (int i = 1; i < s.length(); i++) {
            if (s[i] == s[i-1]) {
                currGroup++;
            } else {
                result += min(prevGroup, currGroup);
                prevGroup = currGroup;
                currGroup = 1;
            }
        }
        
        // 处理最后一对相邻组
        result += min(prevGroup, currGroup);
        
        return result;
    }
};

class Solution:
    def countBinarySubstrings(self, s: str) -> int:
        result = 0
        prev_group = 0
        curr_group = 1
        
        for i in range(1, len(s)):
            if s[i] == s[i-1]:
                curr_group += 1
            else:
                result += min(prev_group, curr_group)
                prev_group = curr_group
                curr_group = 1
        
        # 处理最后一对相邻组
        result += min(prev_group, curr_group)
        
        return result

public class Solution {
    public int CountBinarySubstrings(string s) {
        int result = 0;
        int prevGroup = 0, currGroup = 1;
        
        for (int i = 1; i < s.Length; i++) {
            if (s[i] == s[i-1]) {
                currGroup++;
            } else {
                result += Math.Min(prevGroup, currGroup);
                prevGroup = currGroup;
                currGroup = 1;
            }
        }
        
        // 处理最后一对相邻组
        result += Math.Min(prevGroup, currGroup);
        
        return result;
    }
}

var countBinarySubstrings = function(s) {
    let result = 0;
    let prevGroup = 0, currGroup = 1;
    
    for (let i = 1; i < s.length; i++) {
        if (s[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型大小说明
时间复杂度O(n)只需要遍历字符串一次
空间复杂度O(1)只使用了常数个额外变量

相关题目