1461. Check if a String Contains all Binary Codes of Size K - Explanation

1. Brute Force

Intuition

The most straightforward approach is to generate all possible binary codes of length k and check if each one exists as a substring in the given string s. There are exactly $2^k$ such binary codes (from 0 to $2^k - 1$ ), and we need to verify that every single one appears somewhere in s.

Algorithm

If the length of s is less than $2^k$ , return false immediately since there cannot be enough substrings.
Iterate through all numbers from 0 to $2^k - 1$ .
For each number, convert it to its binary representation with exactly k digits (padding with leading zeros if needed).
Check if this binary string exists as a substring in s.
If any binary code is not found, return false.
If all binary codes are found, return true.

class Solution:
    def hasAllCodes(self, s: str, k: int) -> bool:
        n = len(s)
        if n < (1 << k):
            return False

        for num in range(1 << k):
            binaryCode = format(num, f'0{k}b')
            if binaryCode not in s:
                return False

        return True

Time & Space Complexity

Time complexity: $O(n * 2 ^ k)$
Space complexity: $O(k)$

Where $n$ is the length of the string $s$ and $k$ is the length of the binary code.

2. Hash Set

Intuition

Instead of checking each possible binary code one by one, we can flip the approach: extract all substrings of length k from s and store them in a set. If the set contains exactly $2^k$ unique substrings, then all binary codes are present. This is more efficient because we process each substring only once.

Algorithm

If the length of s is less than $2^k$ , return false immediately.
Create an empty hash set to store unique substrings.
Iterate through s and extract every substring of length k.
Add each substring to the hash set.
After processing all substrings, check if the set size equals $2^k$ .
Return true if the count matches, false otherwise.

class Solution:
    def hasAllCodes(self, s: str, k: int) -> bool:
        if len(s) < 2 ** k:
            return False

        codeSet = set()
        for i in range(len(s) - k + 1):
            codeSet.add(s[i:i + k])

        return len(codeSet) == 2 ** k

Time & Space Complexity

Time complexity: $O(n * k)$
Space complexity: $O(2 ^ k)$

Where $n$ is the length of the string $s$ and $k$ is the length of the binary code.

3. Sliding Window

Intuition

We can improve upon the hash set approach by using bit manipulation to represent each substring as an integer. Instead of storing strings, we maintain a sliding window of k bits. As we move through the string, we update the integer representation by removing the leftmost bit and adding the new rightmost bit. This converts string operations into faster bitwise operations.

Algorithm

If the length of s is less than $2^k$ , return false.
Create a boolean array of size $2^k$ to track which codes have been seen.
Build the initial window by reading the first k characters and converting them to an integer using bit shifts.
Mark the first code as seen and initialize a counter.
Slide the window one character at a time:
- Remove the leftmost bit using XOR if it was 1.
- Shift the current value left by 1.
- Add the new rightmost bit using OR.
- If this code has not been seen before, mark it and increment the counter.
Return true if the counter equals $2^k$ .

class Solution:
    def hasAllCodes(self, s: str, k: int) -> bool:
        n = len(s)
        if n < (1 << k):
            return False

        codeSet = [False] * (1 << k)
        cur = 0
        i = j = 0
        bit = k - 1
        while j < k:
            if s[j] == '1':
                cur |= (1 << bit)
            bit -= 1
            j += 1

        have = 1
        codeSet[cur] = True
        while j < n:
            if s[i] == '1':
                cur ^= (1 << (k - 1))
            i += 1

            cur <<= 1
            if s[j] == '1':
                cur |= 1
            j += 1

            if not codeSet[cur]:
                have += 1
                codeSet[cur] = True

        return have == (1 << k)

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(2 ^ k)$

Where $n$ is the length of the string $s$ and $k$ is the length of the binary code.

4. Sliding Window (Optimal)

Intuition

This approach simplifies the sliding window technique by using a bitmask to automatically handle the window size. Instead of explicitly removing the leftmost bit, we use a bitwise AND with a mask ( $2^k - 1$ ) after shifting. This mask keeps only the rightmost k bits, effectively removing any bits that overflow beyond the window size.

Algorithm

If the length of s is less than $2^k$ , return false.
Create a boolean array of size $2^k$ to track seen codes.
Initialize the current code value and a counter for unique codes found.
Iterate through each character in s:
- Shift the current value left by 1.
- Apply a bitmask (AND with $2^k - 1$ ) to keep only the last k bits.
- Add the current character's bit value using OR.
- Once we have processed at least k characters, check if this code is new.
- If new, mark it as seen and increment the counter.
Return true if the counter equals $2^k$ .

class Solution:
    def hasAllCodes(self, s: str, k: int) -> bool:
        n = len(s)
        if n < (1 << k):
            return False

        codeSet = [False] * (1 << k)
        cur = 0
        have = 0

        for i in range(n):
            cur = ((cur << 1) & ((1 << k) - 1)) | (ord(s[i]) - ord('0'))

            if i >= k - 1:
                if not codeSet[cur]:
                    codeSet[cur] = True
                    have += 1

        return have == (1 << k)

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(2 ^ k)$

Where $n$ is the length of the string $s$ and $k$ is the length of the binary code.

Common Pitfalls

Forgetting the Early Length Check

If the string length is less than k + 2^k - 1, it's impossible to contain all binary codes since there aren't enough substrings. Skipping this check leads to unnecessary computation and potential incorrect results.

# Always check first:
if len(s) < (1 << k):
    return False

Off-by-One Error in Substring Extraction

When iterating to extract substrings of length k, the loop should go from 0 to len(s) - k inclusive. Using range(len(s) - k) instead of range(len(s) - k + 1) misses the last valid substring.

# Wrong: for i in range(len(s) - k)
# Correct:
for i in range(len(s) - k + 1):
    codeSet.add(s[i:i + k])

Incorrect Bitmask in Sliding Window

When using the sliding window approach with bit manipulation, forgetting to mask the result after shifting causes the integer to grow beyond k bits. The mask (1 << k) - 1 must be applied to keep only the last k bits.

# Wrong: cur = (cur << 1) | bit
# Correct:
cur = ((cur << 1) & ((1 << k) - 1)) | bit