Check If a String Contains All Binary Codes of Size K

How it works

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.

Steps

1. If the length of s is less than 2^k, return false.
2. Create a boolean array of size 2^k to track seen codes.
3. Initialize the current code value and a counter for unique codes found.
4. 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.
5. Return true if the counter equals 2^k.

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.

Things to watch for

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.

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.

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.

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)

class Solution {
public:
    bool hasAllCodes(string s, int k) {
        int n = s.size();
        if (n < (1 << k)) {
            return false;
        }

        vector<bool> codeSet(1 << k, false);
        int cur = 0, have = 0;

        for (int i = 0; i < n; i++) {
            cur = ((cur << 1) & ((1 << k) - 1)) | (s[i] - '0');

            if (i >= k - 1) {
                if (!codeSet[cur]) {
                    codeSet[cur] = true;
                    have++;
                }
            }
        }

        return have == (1 << k);
    }
};