Back to solutions

Check if a String Contains all Binary Codes of Size K

MediumArrays

Does the binary string contain every length-k code as a substring?

Open problem
Constraints
  • 1 <= length <= 5*10^5
  • 1 <= k <= 20

Rolling hash of windows

Time O(n)Space O(2^k)

There are 2^k codes of length k. Slide a window of length k and keep its value as a rolling integer (shift left, add the new bit, mask to k bits). Collect distinct window values in a set. If the set's size reaches 2^k, every code appeared.

Key terms
rolling integer:
Maintaining the window's numeric value by shifting in the new bit and dropping the old.
bitmask:
Keeping only the low k bits with an AND so the value stays within k digits.
bool hasAllCodes(const string& s, int k) {
    if ((int)s.size() < k) return false;
    int need = 1 << k, mask = need - 1, cur = 0;
    unordered_set<int> seen;
    for (int i = 0; i < (int)s.size(); i++) {
        cur = ((cur << 1) | (s[i] - '0')) & mask;
        if (i >= k - 1) seen.insert(cur);
    }
    return (int)seen.size() == need;
}
Step by step
  1. If the string is shorter than k, return false.
  2. Slide a k-bit window, updating cur = ((cur<<1) | bit) & mask.
  3. Once a full window exists (i >= k-1), add cur to a set.
  4. Return whether the set has all 2^k distinct codes.