Check If a String Contains All Binary Codes of Size K — Editorial

Opening the reading…

Intuitionwhy every window can be checked as one integer

There are exactly 2^k binary strings of length k. The task is therefore a coverage check: slide a window of length k across s, identify the code in that window, and count how many different codes appear. If the count reaches 2^k, every possible code has been seen. If the scan ends first, at least one code never occurs.

A binary window can be read as a number whose k bits are exactly the characters in the window. For example, 011 has value 3 and 110 has value 6. When the window moves right, shift the old value left, keep only its newest k bits, and append the incoming character. A boolean array indexed by this value records each code without storing substring objects.

Each shift updates the code in constant time instead of rebuilding a substring.

Approach

Return false when k is larger than s.length, because no substring of length k exists and even one required code cannot appear.

Compute needed as 2^k and allocate a boolean array of that size, because every k-bit value is a valid array index from 0 through 2^k - 1.

Build the integer for the first k characters and mark it as seen, because the sliding update starts with an existing full window rather than an empty value.

Set mask to 2^k - 1, whose low k bits are all 1, so each later shift removes every bit older than the current window.

For each remaining character, shift the current code left, apply the mask, and append the new bit, because this changes the window by exactly one position while keeping its length k.

When the new code has not been marked, mark it and increase the distinct count, because repeated windows must not make the coverage count larger than the number of different codes.

Return true immediately when the count reaches 2^k, because all possible codes are covered and scanning later windows cannot change the answer; otherwise return whether the final count reaches that target.

Complexitythe scan is linear and the code universe sets the working memory

MEASURE	BOUND	WHY
Time	O(n)	The initial window is built in O(k), and each of the remaining n - k characters causes one shift, mask, lookup, and possible mark. Since k <= n after the early check, this is O(n), with early success only improving the actual run time.
Space	O(2^k) extra	The seen array has one entry for each possible code; the current integer and counters use O(1) additional space. The required boolean result is not stored as output, so no output storage is being counted. The bound does not degrade with the arrangement of s; it is set by k, reaching 2^20 entries at the largest allowed k.

Here n is the length of s and k is the code length. The value 2^k is the number of possible binary codes.

Annotated solutionC++ · rolling bitmask · complete judge-ready implementation

CPPBuild the first k-bit code, then update it with a masked rolling shift for every later window.

#include <string>
#include <vector>
using namespace std;

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

        int needed = 1 << k;
        vector<bool> seen(needed, false);
        int count = 0;
        int mask = needed - 1;
        int num = 0;

        for (int i = 0; i < k; ++i) {
            num = (num << 1) | (s[i] - '0');
        }

        seen[num] = true;
        ++count;

        for (int i = k; i < n; ++i) {
            num = ((num << 1) & mask) | (s[i] - '0');
            if (!seen[num]) {
                seen[num] = true;
                ++count;
                if (count == needed) {
                    return true;
                }
            }
        }

        return count == needed;
    }
};

The mask is the key placement detail. After num is shifted left, it may contain k + 1 meaningful bits, with the oldest bit belonging to the previous window. Applying mask removes that bit before the incoming character is appended. The seen check comes after the update, so each array access describes exactly one contiguous substring of length k.