首页 > itarticle > algorithm notes: leetcode#696 count binary substrings

algorithm notes: leetcode#696 count binary substrings

admin 11月 12, 2020 0

Problem

Solution

Analysis

Python implementation

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

Java implementation

class  {
    public int countBinarySubstrings(String s) {
        int ans = 0;
        int prev = 0;
        int cur = 1;
        
        for(int i = 1; i < s.length(); i++){
            if(s.charAt(i) != s.charAt(i-1)){
                ans += (prev < cur ? prev : cur);
                prev = cur;
                cur = 1;
            }else{
                cur ++;
            }
        }
        return ans + (prev < cur ? prev : cur);
    }
}

Time complexity

O(N).

Space complexity

O(1).

Links

696. Count Binary Substrings
(中文版) 算法笔记: 力扣#696 计数二进制子串