Python intuitive approaches with explanation (3-liner)


  • 4

    Scroll to the bottom for the 3-liner

    An intuitive approach will be to group the binary string into chunks of 0s and 1s (sort of like compressing). The answer will be simply to sum the min of length of neighboring chunks together.

    Here are some examples:

    • '00001111' => [4, 4] => min(4, 4) => 4
    • '00110' => [2, 2, 1] => min(2, 2) + min(2, 1) => 3
    • '10101' => [1, 1, 1, 1, 1] => 4
    class Solution(object):
        def countBinarySubstrings(self, s):
            chunks, consecutive, res = [], 1, 0
            for i in range(1, len(s)):
                if s[i] == s[i - 1]:
                    consecutive += 1
                else:
                    chunks.append(consecutive)
                    consecutive = 1
            chunks.append(consecutive)
            for i in range(1, len(chunks)):
                res += min(chunks[i], chunks[i - 1])
            return res
    

    An alternative way is to find the positions where the bits flip and we can derive the chunks from the positions of the flips.

    class Solution(object):
        def countBinarySubstrings(self, s):
            flips, res = [0], 0
            for i in range(1, len(s)):
                if s[i] != s[i - 1]:
                    flips.append(i)
            flips.append(len(s))
            chunks = [a - b for (a, b) in zip(flips[1:], flips)]
            for i in range(1, len(chunks)):
                res += min(chunks[i], chunks[i - 1])
            return res
    

    A compressed 3-liner version of the above will look like this:

    class Solution(object):
        def countBinarySubstrings(self, s):
            flips = [0] + [i for i in range(1, len(s)) if s[i] != s[i - 1]] + [len(s)]
            chunks = [a - b for (a, b) in zip(flips[1:], flips)]
            return sum(min(a, b) for a, b in zip(chunks, chunks[1:]))
    

    - Yangshun


Log in to reply
 

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