https://leetcode.com/problems/check-if-a-string-contains-all-binary-codes-of-size-k

Solution 1

Go over all possible substrings of length k and add them to set, and check in the end if the size of our set is 2^k.

Complexity is O(nk), do you know if it can be solved in better complexity?

class Solution:
    def hasAllCodes(self, s, k):
        sset = set()
        for i in range(len(s) - k + 1):
            sset.add(s[i:i+k])
        return len(sset) == 1 << k

If you have any questions, feel free to ask. If you like solution and explanations, please Upvote!

Solution 2

However we can do better. First of all, notice, that k is quite small, so all substrings of length k can fit to int32 number. Let us consider an example:

s = 00110011, k = 3.

Let us look at substrings of length 3 and see how they change when we move:

001 -> 011 -> 110 -> 100 -> 001 -> 011.

Note, that each moment of time we need to multiply number by 2, subtract first symbol multiplied by 2^k and add last symbol. This is called rolling hash, but in fact we just calculate value of number, written in base 2. When we calculate hash, we put it into set and in the end we check if we have 2^k elements in set.

Complexity: time complexity is O(n), we just traverse our string once. Space complexity is O(min(n, 2^k)).

class Solution:
    def hasAllCodes(self, s, k):
        last = int(s[:k], 2)
        ss = {last}
        for i in range(k, len(s)):
            last = last*2 - (int(s[i-k])<<k)  + int(s[i])
            ss.add(last)
        
        return len(ss) == 1<<k

If you like the solution, you can upvote it on leetcode discussion section: Problem 1461