Problem Statement in English

You’re 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.

Approach

Since we know that there are $2^k$ possible binary strings of size k, we can use a set to keep track of the unique substrings of size k that we encounter in s.

We can iterate through the string s and add each substring of size k to the set.

Finally, we check if the size of the set is equal to $2^k$.

And we’re done!

Solution in Python


class Solution:
    def hasAllCodes(self, s: str, k: int) -> bool:
        seen = set()

        for r in range(k, len(s) + 1):
            seen.add(s[r-k:r])
        
        return len(seen) == pow(2, k)

Complexity

  • Time: $O(n \cdot k)$ where $n$ is the length of string s and $k$ is the size of binary strings we’re looking for

  • Space: $O(2^k \cdot k)$ where $2^k$ is the number of unique binary strings of size $k$, and $k$ is the average length of each string in the set

Mistakes I Made

I messed up the slice range.

And we are done.