Check If a String Contains All Binary Codes of Size K

Check If a String Contains All Binary Codes of Size K

What is this problem about?

The "Check If a String Contains All Binary Codes of Size K interview question" asks you to verify if a binary string $s$ contains every possible binary string of length $k$ as a substring. For a given $k$, there are $2^k$ unique binary codes (e.g., if $k=2$, the codes are "00", "01", "10", "11"). Your goal is to determine if all of these are present within $s$.

Why is this asked in interviews?

Companies like Meta and Google ask the "Check If a String Contains All Binary Codes of Size K coding problem" to test a candidate's understanding of string sliding windows and hashing efficiency. It evaluates whether you can recognize that the problem boils down to counting unique substrings of a fixed length. It also tests your knowledge of "Bit Manipulation interview pattern" techniques for representing binary codes as integers to save memory.

Algorithmic pattern used

This problem is best solved using the Sliding Window and Hash Set patterns.

1. Windowing: Slide a window of size $k$ across the binary string $s$.
2. Collect: Extract each substring of length $k$ and add it to a hash set.
3. Optimized Hashing: Instead of storing strings, you can convert each $k$-length window into its integer value using bitwise operations ((current_val << 1) | next_bit and mask with (1 << k) - 1). This is the "Rolling Hash" or "Sliding Window" bitmask trick.
4. Validation: After traversing the entire string $s$, check if the size of the set is equal to $2^k$.

Example explanation

String $s = "00110"$, $k = 2$. Possible codes of size 2: {"00", "01", "10", "11"}. Total expected: 4.

1. Window 1 (index 0-1): "00". Set: {"00"}
2. Window 2 (index 1-2): "01". Set: {"00", "01"}
3. Window 3 (index 2-3): "11". Set: {"00", "01", "11"}
4. Window 4 (index 3-4): "10". Set: {"00", "01", "11", "10"} Set size is 4, which equals $2^2$. Result: True.

Common mistakes candidates make

• String Slicing Inefficiency: Creating a new string object for every window, which can be memory-intensive. Using integers/bitmasks is more efficient.
• Ignoring Constraints: Failing to check if the string $s$ is even long enough to contain all $2^k$ codes ($length(s)$ must be at least $2^k + k - 1$).
• Manual Generation: Trying to generate all $2^k$ codes and searching for each one in $s$, which is $O(2^k imes N)$. The set approach is $O(N)$.

Interview preparation tip

Master the "Rolling Hash" concept. Being able to update the hash of a sliding window in $O(1)$ time is a high-level skill that appears in many "String interview pattern" problems involving fixed-length patterns.