696. Count Binary Substrings

Description

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.

Solution

Slide window, time O(n), space O(1)

初始的想法就是找到两个元素不同的位置，然后往两边扩散。

class Solution {
    public int countBinarySubstrings(String s) {
        if (s == null || s.length() < 2) {
            return 0;
        }
        
        char[] arr = s.toCharArray();
        int i = 0;
        int len = s.length();
        int count = 0;
        while (i < len - 1) {
            if (arr[i] == arr[i + 1]) {
                ++i;
                continue;
            }
            
            ++count;
            int j = i + 1;
            while (i > 0 && j < len - 1 && arr[i - 1] == arr[i] && arr[j + 1] == arr[j]) {
                ++count;
                --i;
                ++j;
            }
            
            i = j;
        }
        
        return count;
    }
}

time O(n), space O(1)

这是一个蛮有意思的解法

• preRun count the same item happend before (let say you have 0011, preRun = 2 when you hit the first 1, means there are two zeros before first ‘1’)
• curRun count the current number of items (let say you have 0011, curRun = 2 when you hit the second 1, means there are two 1s so far)
• Whenever item change (from 0 to 1 or from 1 to 0), preRun change to curRun, reset curRun to 1 (store the curRun number into PreRun, reset curRun)
• Every time preRun >= curRun means there are more 0s before 1s, so could do count++ . (This was the tricky one, ex. 0011 when you hit the first ‘1’, curRun = 1, preRun = 2, means 0s number is larger than 1s number, so we could form “01” at this time, count++ . When you hit the second ‘1’, curRun = 2, preRun = 2, means 0s’ number equals to 1s’ number, so we could form “0011” at this time, that is why count++)

class Solution {
    public int countBinarySubstrings(String s) {
        if (s == null || s.length() < 2) {
            return 0;
        }
        
        int preRun = 0;
        int curRun = 1;
        int count = 0;
        
        for (int i = 1; i < s.length(); ++i) {
            if (s.charAt(i) == s.charAt(i - 1)) {
                ++curRun;
            } else {
                preRun = curRun;
                curRun = 1;
            }
            
            if (preRun >= curRun) {
                ++count;
            }            
        }
        
        return count;
    }
}