696. Count Binary Substrings

---

Give a string s, count the number of non-empty (contiguous) substrings that have the same number of 0's and 1's, and all the 0's and all the 1's in these substrings are grouped consecutively.

Substrings that occur multiple times are counted the number of times they occur.

Example 1:

Input: "00110011"

Output: 6

Explanation: There are 6 substrings that have equal number of consecutive 1's and 0's: 
             "0011", "01", "1100", "10", "0011", and "01".

Notice that some of these substrings repeat and are counted the number of times they occur.

Also, "00110011" is not a valid substring because all the 0's (and 1's) are not grouped together.

Example 2:

Input: "10101"

Output: 4

Explanation: There are 4 substrings: "10", "01", "10", "01" that have equal number of consecutive 1's and 0's.

Note:

• s.length will be between 1 and 50,000.
• s will only consist of "0" or "1" characters.

---

解法1

首先, 每个类似于000111的字符串,都一定有3个符合条件的字符串 000111, 0011 和01, 所以问题就变成了按照顺序找到所有最长的满足条件的字字符串

然后, 就是怎么计数的问题. 可以观察到, 每次都是在0变1 或者1变0 的时候, 去比较之前的连续0 和连续1的个数,较小的那个就是需要的结果. 得到结果之后,清空靠前字符的计数器,重新计数.比如0001100..., 在1变0的时候,得到结果2, 然后1的计数器不变,0的计数器清零,然后设置为1, 继续计算.

class Solution {
    public int countBinarySubstrings(String s) {
        // 0 和 1 的计数器
        int count_0 = 0, count_1 = 0;
        // 结果
        int res = 0;
        // 前一个字符(默认是0)
        char pre = '0';
        
        // 第一个字符单独计数
        if(s.charAt(0) == '0')
            count_0 = 1;
        else{
            count_1 = 1;
            // 如果是1的话, pre设置为1
            pre = '1';
        }
            
        
        for(int i= 1; i < s.length(); i++){
            char cur = s.charAt(i);
            // 当和前一个字符相等时,对应的计数器加1
            if(cur == pre){
                if(cur == '0')
                    count_0++;
                else
                    count_1++;
            }
            // 当和前一个字符不相等时
            else{
                // 取较短的串的长度, 加入结果
                res += Math.min(count_0, count_1);
                pre = cur;
                if(cur == '0'){
                    count_0 = 1;
                }else
                    count_1 = 1;
            }
        }

        return res + Math.min(count_0, count_1) ;        
    }
}

---

解法2

lee215大神的解法看的我一脸懵逼.真的是,我就是个sb.

大神的解法

其实基本思路是一样的, 但是不知道要高明到哪里去了.

不用老老实实的去判断是0 还是1, 只需要和前一个去比就好了.

class Solution {
    public int countBinarySubstrings(String s) {
        int cur = 1, pre = 0, res = 0;
        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) == s.charAt(i - 1)) cur++;
            else {
                res += Math.min(cur, pre);
                pre = cur;
                cur = 1;
            }
        }
        return res + Math.min(cur, pre);
    }
}