696. Count Binary Substrings

https://leetcode.com/problems/count-binary-substrings/

solution

• 注意是连续，因此不能用hash存储个数来判断

• 分别处理与前值相同、与前值不同的场景. 构思还是非常巧妙的

class Solution:
    def countBinarySubstrings(self, s: str) -> int:
        pre = 0  # 前一类的个数
        cur = 1  # 本类的个数
        count = 0
        for i in range(1, len(s)):
            if s[i] == s[i-1]:
                cur += 1
            else:
                pre = cur
                cur = 1
            
            if pre >= cur:
                count += 1
        return count

时间复杂度：O(n) 空间复杂度：O(1)