计算二进制子串

696. 计数二进制子串

给定一个字符串 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”字符。

我们可以将字符串 s 按照 0 和 1 的连续段分组，存在 counts 数组中，例如 s = 00111011，可以得到 counts = {2, 3, 1, 2}。

counts 数组中两个相邻的数一定为两种不同的字符。假设 counts 数组中相邻的两个数字为 u 和 v，那么可能为 u 个 0 ，v 个 1 或 u 个 1 ，v 个 0，这一对数字对答案的贡献为 min{u, v}。我们遍历所有相邻的数对，计算它们的贡献和。

class Solution {
    public int countBinarySubstrings(String s) {
        List<Integer> counts = new ArrayList<>();
        int ans = 0;
		//生成 counts 数组
        char cur = s.charAt(0);
        int c = 0;
        for(int i = 0; i < s.length(); i++){
            if(s.charAt(i) == cur){
                ++c;
            }else{
                counts.add(c);
                cur = s.charAt(i);
                c =  1;
            }
        }
        counts.add(c);
        //计算贡献和
        for(int i = 1; i < counts.size(); i++){
            ans += Math.min(counts.get(i), counts.get(i - 1));
        }
        return ans;
    }

}

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

我们可以发现，在对每一个数计算贡献时，我们只用到了前一个值，我们使用 last 来保存。

class Solution {
    public int countBinarySubstrings(String s) {
        int ptr = 0, n = s.length(), last = 0, ans = 0;
        while(ptr < n){
            char c = s.charAt(ptr);
            int count = 0;
            while(ptr < n && s.charAt(ptr) == c){
                ++ptr;
                ++count;
            }

            ans += Math.min(count, last);
            last = count;
        }
        return ans;
    }

}

时间复杂度O(n)，空间复杂度O(1)。