696. Count Binary Substrings

1.暴力法, 找出所有 substring, then count 1's count equal 0's count, but 0,1是要連續出現的

其實看 0 or 1 出現的連續行為

ex: 10101 ⇒ substring, 1010 ⇒ 不對喔！ 0 或 1 要 group 連續出現

2. run length... 其實非常不好想

Run Length

time: O(n)

space: O(1)

思路

1. s(i) = s(i-1) ⇒ 判斷是否連續一樣

2. 不一樣的時候 ⇒ 1. 更新 pre, 2 更新 cur

ex : 0 0 1 1 ⇒ 到1 時, 不一樣了, 這時候 cur 還是 00,

do pre = cur

cur = 1

⇒ pre: 00, cur = 1

ex. 0011

hit the first '1'

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++ .

hit the second '1',

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() == 0) return 0;
        
        int res = 0;
        int prev = 0;
        int cur = 1;
        
        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) == s.charAt(i-1)) { // i from 1 
                cur++;
            } else {
                prev = cur;
                cur = 1;
            }
            if (prev >= cur) { // 這樣可以計算到所有的結果
                res++;
            }
        }
        return res;
    }
}