Generated by Codex with GPT 5.6 Sol High

Quick facts

The problem in one sentence

Given a binary string s and a length k, determine whether every one of the $2^k$ possible binary strings of length k appears somewhere as a contiguous substring of s.

For example, when k = 2, the required codes are 00, 01, 10, and 11. They may overlap inside s; each starting position contributes one length-k window.

Start with the counting lower bound

A string of length $n$ contains exactly $n-k+1$ windows of length k when $n \ge k$. There are $2^k$ different codes to find, and one window can represent only one code. Therefore, if

$$ n-k+1 < 2^k, $$

the answer must be False. This check is both a useful proof step and a practical optimization: it avoids allocating the tracking table when the input is too short to succeed.

Passing the check does not prove that all codes exist, because several windows may be duplicates. The remaining task is to scan the windows and count how many distinct codes actually occur.

Turn each window into an integer

A length-k binary code is naturally an integer from 0 through $2^k-1$. As the window moves one position to the right:

  1. Shift the current integer left by one bit.
  2. Discard the bit that fell outside the last k positions by applying the mask $2^k-1$.
  3. Add the new character as the low bit.

For s = "00110110" and k = 2, the successive window values are 00, 01, 11, 10, 01, 11, and 10. Marking those integer indices discovers all four possible values without constructing any substring copies.

A bytearray is a compact exact membership table: index code is 1 once that code has appeared. A counter tracks how many unseen codes remain, allowing the scan to return immediately when the counter reaches zero. Unlike a conventional rolling hash, this encoding has no collision risk because the bits of the window are the integer itself.

Python solution

class Solution:
    def hasAllCodes(self, s: str, k: int) -> bool:
        """Return whether s contains every binary substring of length k."""
        total_codes = 1 << k
        window_count = len(s) - k + 1

        # Each window can contribute at most one distinct code.
        if window_count < total_codes:
            return False

        seen_codes = bytearray(total_codes)
        unseen_count = total_codes
        window_mask = total_codes - 1
        window_value = 0

        for index, character in enumerate(s):
            incoming_bit = 1 if character == "1" else 0
            window_value = ((window_value << 1) & window_mask) | incoming_bit

            # The rolling value represents a full window only after k bits.
            if index < k - 1:
                continue

            if seen_codes[window_value] == 0:
                seen_codes[window_value] = 1
                unseen_count -= 1

                if unseen_count == 0:
                    return True

        return False

The scan takes $O(n)$ time. Initializing the membership table takes $O(2^k)$ time and space; whenever allocation is reached, the lower-bound check guarantees $2^k \le n-k+1$, so the total running time is $O(n)$ under the problem constraints. Auxiliary space is $O(2^k)$.

Why the algorithm is correct

After processing any full window, window_value is exactly the integer represented by that window’s last k bits. The mask removes every older bit, so no character outside the current window can affect the value.

The membership table is updated at precisely that integer index. Consequently, unseen_count decreases once for each distinct length-k code found and never decreases for a duplicate. It reaches zero if and only if all $2^k$ codes have appeared. If the scan ends with a positive count, at least one code is absent, so returning False is correct.

Interview follow-ups

Why is the initial window-count check valid?

There are $2^k$ distinct target codes but only $n-k+1$ length-k windows. Even though windows may overlap, each particular window still equals only one code. If the number of windows is smaller than the number of required codes, the pigeonhole principle makes success impossible.

The check takes $O(1)$ time and lets the function reject short inputs before using $O(2^k)$ memory. It is only a necessary condition: having enough windows does not prevent duplicates, so a scan is still required.

Could this be solved with a set of substrings?

Yes. Insert every slice s[start:start + k] into a set and test whether the set reaches size $2^k$. This is often the simplest solution to explain first.

In Python, however, creating and hashing a slice costs up to $O(k)$ time and stores copied string data, leading to $O(nk)$ work in the straightforward analysis and up to $O(k2^k)$ stored characters. The rolling integer solution processes each new character in $O(1)$ time and uses one byte per possible code.

Can the membership structure use fewer bits?

Yes. A packed bitset needs exactly one bit per possible code instead of the one byte per code used by bytearray. To mark code x, use word index x // word_size and bit position x % word_size.

This preserves $O(n)$ time and $O(2^k)$ asymptotic space while improving the constant factor by roughly eight. The bytearray version is usually preferable in an interview because it is already compact and considerably clearer.

How would the solution return all missing codes?

Run the same rolling scan, then inspect every index whose membership byte is still zero. Convert each missing index to a zero-padded binary string of width k, for example with format(code, f"0{k}b").

The scan still takes $O(n)$ time, but enumerating the table adds $O(2^k)$ checks and producing the strings can require $O(k2^k)$ output space. That extra cost is unavoidable when many codes are missing because the requested output itself is that large.

What changes for an alphabet larger than binary?

For an alphabet of size $b$, map each character to a digit from 0 through $b-1$ and treat each length-k window as a base-$b$ integer. Update it with

window_value = (window_value * b + incoming_digit) % (b ** k).

There are $b^k$ possible codes, so the same window-count lower bound, membership table, and early success condition apply. The algorithm takes $O(n)$ time and $O(b^k)$ space, assuming constant-time arithmetic for the bounded encoded values.

What if the input arrives as a stream?

Only the rolling integer, the membership table, and the count of processed characters are needed. Characters can therefore be consumed one at a time without retaining the full string, and the algorithm can report success as soon as all codes have appeared.

The time and membership-space bounds remain unchanged. If the stream ends first, the positive unseen_count proves that at least one code never arrived.

Is there a mathematical description of the shortest successful string?

Yes. Since a string with $2^k$ distinct length-k windows must have length at least $2^k+k-1$, that is a universal lower bound. A linearized binary de Bruijn sequence meets it by arranging every length-k binary code exactly once as a cyclic window and then appending its first k-1 characters.

Constructing such a string is a different problem, typically solved with an Eulerian cycle in a graph of length-k-1 binary strings. Its output has optimal length, while the recognition problem here only needs to verify a supplied string.

Takeaway

The key is to count distinct fixed-length windows without copying them. Encoding each binary window as its own integer gives an exact rolling representation, and a compact membership table turns the problem into one linear pass. The counting lower bound explains both the early rejection and why the exponential-looking table is still bounded by the input size whenever success is possible.