696. 计数二进制子串

点击上方链接跳转至leetcode

题目描述

给定一个字符串 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 <= 105
• s[i] 为 '0' 或 '1'

解法

我们可以将字符串 ss 按照 00 和 11 的连续段分组，存在counts数组中，例如 s = 00111011，可以得到这样的 counts 数组: counts={2,3,1,2}。
这里counts数组中两个相邻的数一定代表的是两种不同的字符。假设counts数组中两个相邻的数字为u或者v，它们对应着u个00 和 v 个 11，或者u 个 11 和v 个 00。它们能组成的满足条件的子串数目为min{u,v}，即一对相邻的数字对答案的贡献。
我们只要遍历所有相邻的数对，求它们的贡献总和，即可得到答案。

Python3

from typing import List    

class Solution:
    def countBinarySubstrings(self, s: str) -> int:
        i, n = 0, len(s)
        t = []
        while i < n:
            cnt = 1
            while i + 1 < n and s[i + 1] == s[i]:
                cnt += 1
                i += 1
            t.append(cnt)
            i += 1
        ans = 0
        for i in range(1, len(t)):
            ans += min(t[i - 1], t[i])
        return ans


fun = Solution()
s = "00110011"
res = fun.countBinarySubstrings(s)
print(res)

C++

#include<iostream>
#include<string>
#include<vector>
using namespace std;

class Solution{
public:
    int countBinarySubstrings(string s) {
        int i =0,n = s.size();
        vector<int> t;
        while(i<n){
            int cnt = 1;
            while(i+1 < n && s[i+1] == s[i]){
                ++cnt;
                ++i;
            }
            t.push_back(cnt);
            ++i;
        }
        int ans = 0;
        for(i =1;i<t.size();++i)
            ans += min(t[i-1],t[i]);
        return ans;
    }
};

int main(){

    string s= "00110011";
    int res = Solution().countBinarySubstrings(s);
    cout << "res: " << res << endl;

    return  0;
}

//g++ 696.cpp -std=c++11

复杂度分析：

时间复杂度和空间复杂度都是O(n)。