1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int countBinarySubstrings(String s) {
        int prev = 0, curr = 1, ans = 0;
        char[] sArray = s.toCharArray();
        for (int i = 1; i < sArray.length; i++) {
            if (sArray[i] == sArray[i - 1]) {
                curr += 1;
            } else {
                ans += Math.min(prev, curr);
                prev = curr;
                curr = 1;
            }
        }
        ans += Math.min(prev, curr);
        return ans;
    }
}

能够构成满足题意的substring中间的分界线一定是01或者10这样的. 然后往两边扩散. 看能扩散多少. 既然我们是从左往右遍历, 我们可以记录遇到的0或者1的连续出现的次数, 然后等碰到一个不同的字符的时候, 再记录它连续出现的次数, 这样就能直接知道substring的个数了, 此时substring的个数就是扩散到两头最远的距离(前提是保证两端都有相互对应的字符), 反映下来就是看两侧哪个字符重复的次数低, 这就是此时substrings的个数.

这道题的解题关键就是找到分界点(01或者10), 看每个分界点能构成多少substrings而不是遍历所有的substrings去找符合条件的.

时间复杂度: O(n)
空间复杂度: O(1) 虽然我用了一个char array但是不用也行, 用的话运行的速度很快.