696. Count Binary Substrings

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.

My Solutions:

How many valid binary substrings exist in "000111", and how many in "11100"? What about "00011100"?

000111：有3个合格的字符串，000111， 0011， 01

11100：有2个合格的字符串，1100， 10

00110011：可以分解为0011（2个），1100（2个），0011（2个），总共有6个合格的字符串。

所以，合格字符串的数量和连续出现的1或0有关。取连续的1或0中，次数较小的。

定义变量ans用来记录子串次数，变量pre存储当前数字前的数字连续次数，变量cur存储当前数字的连续次数。

接着从第二个数字开始遍历，

• 如果当前数字与前面数字相同，cur++；

• 如果数字不同，对pre和cur取最小值(只能组成最小值的次数的binary string），记为子串次数加在ans上，同时pre变成cur，cur变成1。

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