Cacher is the code snippet organizer for pro developers

# Time: O(n)   
# Space: O(n)
# 696. Count Binary Substrings
# Notes: https://i.imgur.com/rGdjF0f.png


class Solution3(object):
    def countBinarySubstrings(self, s):
        """
        :type s: str
        :rtype: int
        """
        pre, cur, ans = 0, 1, 0
        for i in range(1, len(s)):
            if s[i-1] == s[i]:
                cur += 1
            else:
                ans += min(pre, cur)
                pre, cur = cur, 1
        
        return ans + min(pre, cur)

# Time: O(2n)
# Space: O(n)
class Solution2(object):
    def countBinarySubstrings(self, s):
        """
        :type s: str
        :rtype: int
        """
        groups = [1]
        for i in range(1, len(s)):
            if s[i-1] == s[i]:
                groups[-1] += 1
            else:
                groups.append(1)
                
        ans = 0
        for i in xrange(1, len(groups)):
            ans += min(groups[i-1], groups[i])
        return ans
    
    
# Time: O(n^2)
# Space: O(n)
class Solution1(object):
    def countBinarySubstrings(self, s):
        """
        :type s: str
        :rtype: int
        """
        result = 0
        for i in range(len(s)-1):
            j = i + 1
            count = 1
            flag = 0 
            while count > 0 and flag <= 1 and j < len(s):
                if s[j] != s[j-1]:
                    flag += 1
                    
                if flag == 0:
                    count += 1
                elif flag == 1: 
                    count -= 1
                    
                if count == 0:
                    result += 1
                j += 1
        return result