Python solution with detailed explanation


  • 0
    G

    Count Binary Substrings https://leetcode.com/problems/count-binary-substrings/description/

    Encode the input and scan

    • Encode "00110011" as encoding = [2,2,2,2].
    • How many valid strings possible between encoding[i-1] and encoding[i]? Example between "0001111111" will be encoded as [3,7] and will result in "01", "0011", and "000111". We can see that this results in min(3,7) or 3.
    • O(N) time and O(N) space.
    class Solution:
        def countBinarySubstrings(self, s):
            """
            :type s: str
            :rtype: int
            """
            encoding, prev = [], None
            for ch in s:
                if prev is not None and prev == ch:
                    encoding[-1] += 1
                else:
                    encoding.append(1)
                prev = ch
            result = 0
            for i in range(1, len(encoding)):
                result += min(encoding[i-1], encoding[i])
            return result
    

    Modify and maintain count of previos run and scan

    • Instead of encoding entire array, we just need to remember the length of the previos run.
    • O(N) time and O(1) space.
    class Solution:
        def get_run(self, start, s):
            run = 0
            ch  = s[start]
            while start < len(s) and s[start] == ch:
                start, run = start+1, run+1
            return start, run
        
        def countBinarySubstrings(self, s):
            """
            :type s: str
            :rtype: int
            """
            start, prev_run, result  = 0, 0, 0
            while start < len(s):
                start, curr_run = self.get_run(start, s)
                result += min(prev_run, curr_run)
                prev_run = curr_run
            return result
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.