Check if a String Contains All Binary Codes of Size K

medium string hash set sliding window bit manipulation

Problem

Given a binary string s and an integer k, return true if every binary code of length k is a substring of s. Otherwise, return false.

There are exactly 2^k distinct binary codes of length k. Collect every length-k substring of s into a set; if the set ends up holding all 2^k of them, the answer is true.

Inputs = "00110110", k = 2

Outputtrue

The length-2 substrings are 00, 01, 11, 10 — all four 2-bit codes appear.

s (binary)

def has_all_codes(s, k):
    need = 1 << k
    seen = set()
    for i in range(len(s) - k + 1):
        sub = s[i:i + k]
        if sub not in seen:
            seen.add(sub)
            if len(seen) == need:
                return True
    return len(seen) == need

function hasAllCodes(s, k) {
  const need = 1 << k;
  const seen = new Set();
  for (let i = 0; i + k <= s.length; i++) {
    const sub = s.slice(i, i + k);
    if (!seen.has(sub)) {
      seen.add(sub);
      if (seen.size === need) return true;
    }
  }
  return seen.size === need;
}

class Solution {
    public boolean hasAllCodes(String s, int k) {
        int need = 1 << k;
        Set<String> seen = new HashSet<>();
        for (int i = 0; i + k <= s.length(); i++) {
            String sub = s.substring(i, i + k);
            if (seen.add(sub) && seen.size() == need) {
                return true;
            }
        }
        return seen.size() == need;
    }
}

bool hasAllCodes(string s, int k) {
    int need = 1 << k;
    unordered_set<string> seen;
    for (int i = 0; i + k <= (int)s.size(); i++) {
        string sub = s.substr(i, k);
        seen.insert(sub);
        if ((int)seen.size() == need) return true;
    }
    return (int)seen.size() == need;
}

Explanation

There are precisely 2^k different binary strings of length k. The question reduces to: does s contain all of them as substrings? We never need to enumerate the codes — we just need to count how many distinct ones actually show up.

We slide a window of width k from left to right. Each position i gives the substring s[i .. i+k-1], which we add to a hash set. The set automatically de-duplicates, so its size is the number of unique codes seen so far.

The earliest we could possibly have all of them is once the set's size reaches need = 2^k. The moment that happens we can short-circuit and return true — no later window can change the verdict.

If the loop finishes and the set is still smaller than 2^k, at least one code is missing, so we return false. A quick early-out: if s is shorter than 2^k + k - 1 there simply are not enough windows, but the set-size check handles that case naturally too.

Example: s = "00110110", k = 2, so need = 4. The windows produce 00, 01, 11, 10, 01, 11, 10 — the set fills to {00, 01, 11, 10} and we return true as soon as it reaches size 4.

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