696. Count Binary Substrings

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

Count Binary Substrings - LeetCode

idea: convert into [group_cnt, group_cnt, ... ]

 

290ms

import collections

class Solution:
    def countBinarySubstrings(self, s: str) -> int:
        
        buf = []
        is_zero = (s[0] == '0')
        cnt = 1
        for c in s[1:]:
            if is_zero:
                if c == '0':
                    cnt += 1
                else:
                    is_zero = False
                    buf.append(cnt)
                    cnt = 1
            else:
                if c == '1':
                    cnt += 1
                else:
                    is_zero = True
                    buf.append(cnt)
                    cnt = 1
        buf.append(cnt)
        
        ret = 0
        for i in range(1, len(buf)):
            left = buf[i-1]
            right = buf[i]
            equal = min(left, right)*2
            ret += int(equal/2)
        
        return ret

 

not use buffer

loop only 1

 

112ms

class Solution:
    def countBinarySubstrings(self, s: str) -> int:
        if not s:
            return 0
        else:
            x=0
            if(s[0]=='0'):
                flag='0'
            else:
                flag='1'
            c=0
            p=0
            for ele in s:
                if(ele==flag):
                    c+=1
                else:
                    x+=min(c,p)
                    p=c
                    c=1
                    flag=ele
                       
            x+=min(p,c)
            return x

100ms

class Solution:
    def countBinarySubstrings(self, s):
        s = list(map(len, s.replace('01', '0 1').replace('10', '1 0').split()))
        return sum(min(a, b) for a, b in zip(s, s[1:]))