Count_Binary_Substrings.md

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.

Code:

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

解题思路

• 维护两个变量preRunLen和curRunLen；
• preRunLen存储的是前不同元素（假如是0）连续出现的个数，curRunLen存储的是当前元素（假如是1）连续出现的个数；
• 例如，对于0011的情况。当遍历到第一个1时，preRunLen就等于2，curRunLen就重置为1；
• 每当前一元素连续出现的个数大于等于当前元素连续出现的个数时，res加一。两计数器相等，符合情况；大于时也有满足条件的情况。