Time limit exceeded on the code: Check If a String Contains All Binary Codes of Size K

Question

I'm trying to solve LeetCode problem 1461. Check If a String Contains All Binary Codes of Size K:

Given a binary string s and an integer k, return true if every binary code of length k is a substring of s. Otherwise, return false.

Thought process

Make a list of all possible binary strings of length k (named it binary). Then iterate through the string with sliding windows, and for every window check if that exists in the list called binary. If the list is empty it means it satisfied all possible strings. If it's not empty that means it didn't include all the possible binary codes and will return false.

Code

class Solution(object):
    def hasAllCodes(self, s, k):
        """
        :type s: str
        :type k: int
        :rtype: bool
        """
        if k > len(s):
            return False
        binary = [""]
        for i in range(k):
            N = len(binary)
            for i in range(N):
                a = binary.pop(0)
                binary.append(a + "0")
                binary.append(a + "1")

        n=len(s)
        i=j=0
        sSoFar=""
        while j<n:
            sSoFar+=s[j]
            if j>=k-1:
                if sSoFar in binary:
                    binary.remove(sSoFar)
                sSoFar=sSoFar[1:]
                i+=1
            j+=1


        #print(binary)
        return len(binary)==0


solution = Solution()
a = solution.hasAllCodes("00110110", 2) #expected true
print(a)
a = solution.hasAllCodes("0110", 1) #expected true
print(a)
a = solution.hasAllCodes("0110", 2) #expected false
print(a)
a = solution.hasAllCodes("1011110111001001101001110001100111101111010101011100111001110010010001000111010110101110000110101001011100100010100110011101011110001000100010101101011", 20) #expected false
print(a)

Issue

I get a time limited exceeded error on the last test included in above code snippet. What should I improve on?

Answer 1

The list pop(0) and remove methods have a bad time complexity.

It is more efficient to work with a set, and let it be a set of int instead of strings. It will also be faster if you start with an empty set, and add the values to it that you find while scanning the input string.

Keep track of what the value is of the k-size "window" you're inspecting in the main loop. When the window slides one position forward, you can easily update the value by:

1. multiplying it with 2 to make room for the new digit
2. adding the new digit to it (as either 0 or 1)
3. Dropping the "old" digit, by using a modulo operation (or applying a bit mask)

Then add these values to a set. You can see from the size of that set whether all binary numbers were collected or not.

Here is a spoiler solution:

def hasAllCodes(self, s, k): binary = set() # Start with empty set. n = len(s) value = int("0" + s[:k-1], 2) # Avoid error when k=1 and prepad a zero mod = 1 << k # This is 2**k, but as an integer operation for digit in s[k-1:]: value = (value * 2 + int(digit)) % mod # Slide the window binary.add(value) if len(binary) == mod: # We found all binary numbers? return True return False

Answer 2

A simpler solution is to just use a set comprehension to get all the distinct substrings of length k and check the size of that set.

class Solution(object):
    def hasAllCodes(self, s, k):
        return len({s[i:i+k] for i in range(len(s) - k + 1)}) == 1 << k