Problem of The Day: Count Binary Substrings

2 min read 442 words

Problem Statement

leetcode problem link

Solution [Accepted]

class Solution:
    def countBinarySubstrings(self, s: str) -> int:
        res = 0
        N = len(s)
        for i in range(1, N):
            l, r = i - 1, i
            leftChar = s[l]
            rightChar = s[r]
            while l >= 0 and r < N and s[l] != s[r] and s[l] == leftChar and s[r] == rightChar:
                res += 1
                l -= 1
                r += 1

        return res

• time: O(n^2)
• space: O(1)

Editorial

Approach #1: Group By Character [Accepted]

class Solution(object):
    def countBinarySubstrings(self, s):
        groups = [1]
        for i in range(1, len(s)):
            if s[i-1] != s[i]:
                groups.append(1)
            else:
                groups[-1] += 1

        ans = 0
        for i in range(1, len(groups)):
            ans += min(groups[i-1], groups[i])
        return ans

Approach #2: Linear Scan [Accepted]

class Solution(object):
    def countBinarySubstrings(self, s):
        ans, prev, cur = 0, 0, 1
        for i in xrange(1, len(s)):
            if s[i-1] != s[i]:
                ans += min(prev, cur)
                prev, cur = cur, 1
            else:
                cur += 1

        return ans + min(prev, cur)