README.md

696. 计数二进制子串

English Version

题目描述

给定一个字符串 s，计算具有相同数量 0 和 1 的非空（连续）子字符串的数量，并且这些子字符串中的所有 0 和所有 1 都是连续的。

重复出现的子串要计算它们出现的次数。

 

示例 1 :

输入: "00110011"
输出: 6
解释: 有6个子串具有相同数量的连续1和0：“0011”，“01”，“1100”，“10”，“0011” 和 “01”。

请注意，一些重复出现的子串要计算它们出现的次数。

另外，“00110011”不是有效的子串，因为所有的0（和1）没有组合在一起。

示例 2 :

输入: "10101"
输出: 4
解释: 有4个子串：“10”，“01”，“10”，“01”，它们具有相同数量的连续1和0。

 

提示：

• s.length 在1到50,000之间。
• s 只包含“0”或“1”字符。

解法

Python3

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

Java

class Solution {
    public int countBinarySubstrings(String s) {
        int i = 0, n = s.length();
        List<Integer> t = new ArrayList<>();
        while (i < n) {
            int cnt = 1;
            while (i + 1 < n && s.charAt(i + 1) == s.charAt(i)) {
                ++i;
                ++cnt;
            }
            t.add(cnt);
            ++i;
        }
        int ans = 0;
        for (i = 1; i < t.size(); ++i) {
            ans += Math.min(t.get(i - 1), t.get(i));
        }
        return ans;
    }
}

C++

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

Go

func countBinarySubstrings(s string) int {
	i, n := 0, len(s)
	var t []int
	for i < n {
		cnt := 1
		for i+1 < n && s[i+1] == s[i] {
			i++
			cnt++
		}
		t = append(t, cnt)
		i++
	}
	ans := 0
	for i := 1; i < len(t); i++ {
		ans += min(t[i-1], t[i])
	}
	return ans
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

...