Check If a String Contains All Binary Codes of Size K

Medium
1217.

Check If a String Contains All Binary Codes of Size K

Check If a String Contains All Binary Codes of Size K is a medium coding problem on strings, hash table and bit manipulation, asked in Amazon and Google interviews.

Given a binary string s and an integer k, return true if every binary code of length k — all 2^k strings of k zeros and ones — appears in s as a substring. Otherwise return false.

Example 1

Input
s = "00110100", k = 2
Output
true
Explanation
`00`, `01`, `11` and `10` all appear.

Example 2

Input
s = "0101", k = 2
Output
false
Explanation
`00` and `11` are missing.

Example 3

Input
s = "10", k = 1
Output
true

Constraints

  • 1 <= s.length <= 5 * 10^5
  • s[i] is '0' or '1'
  • 1 <= k <= 20
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @param {number} k
 * @return {boolean}
 */
var hasAllCodes = function(s, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Check If a String Contains All Binary Codes of Size K Solution

Check If a String Contains All Binary Codes of Size K solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Check If a String Contains All Binary Codes of Size K is a medium coding problem on strings, hash table and bit manipulation, asked in Amazon and Google interviews.

Problem statement

Given a binary string s and an integer k, return true if every binary code of length k — all 2^k strings of k zeros and ones — appears in s as a substring. Otherwise return false.

Example 1

Input: s = "00110100", k = 2
Output: true
Explanation: `00`, `01`, `11` and `10` all appear.

Example 2

Input: s = "0101", k = 2
Output: false
Explanation: `00` and `11` are missing.

Example 3

Input: s = "10", k = 1
Output: true

Constraints

  • 1 <= s.length <= 5 * 10^5
  • s[i] is '0' or '1'
  • 1 <= k <= 20

Hints for Check If a String Contains All Binary Codes of Size K

  1. Hint 1

    s has only n − k + 1 substrings of length k; if that is fewer than 2^k, the answer is false at once.

  2. Hint 2

    Collect the distinct length-k windows and compare their number with 2^k.

  3. Hint 3

    Read each window as a k-bit number and update it in O(1) when the window slides: shift left, add the new bit, mask to k bits.

How to solve Check If a String Contains All Binary Codes of Size K

All codes are present exactly when the set of length-k windows has 2^k elements; a rolling k-bit integer makes each window O(1) to compute and a boolean array of size 2^k records them.

Approach

  1. Let need = 2^k. If n − k + 1 < need, return false.
  2. Keep cur, the value of the last k bits read, and a boolean array seen of size need.
  3. For each bit, set cur = ((cur << 1) | bit) & (need − 1); once at least k bits have been read, mark seen[cur] and count it if it was new.
  4. Return true as soon as the count reaches need, or false at the end.

Why it works

Masking to the low k bits keeps cur equal to the window ending at the current position, read as a binary number, so distinct windows map to distinct indices of seen. The early length check is not only a speed-up — it also keeps the array no larger than the string itself.

Complexity

  • Time — O(n)
  • Space — O(2^k), at most O(n) thanks to the early check

Pitfalls

  • Hashing substrings costs O(k) each; the rolling integer avoids that.
  • Counting windows before k bits have been read marks codes that do not exist.
  • k may exceed n — then there are no windows at all.

Reference solution

Python

def hasAllCodes(s: str, k: int) -> bool:
    need = 1 << k
    if len(s) - k + 1 < need:
        return False
    return len({s[i:i + k] for i in range(len(s) - k + 1)}) == need

Java

public static boolean hasAllCodes(String s, int k) {
    int need = 1 << k;
    if (s.length() - k + 1 < need) return false;
    boolean[] seen = new boolean[need];
    int mask = need - 1, cur = 0, count = 0;
    for (int i = 0; i < s.length(); i++) {
        cur = ((cur << 1) | (s.charAt(i) - '0')) & mask;
        if (i >= k - 1 && !seen[cur]) {
            seen[cur] = true;
            if (++count == need) return true;
        }
    }
    return false;
}

C++

bool hasAllCodes(string s, int k) {
    int need = 1 << k;
    if ((int)s.size() - k + 1 < need) return false;
    vector<bool> seen(need, false);
    int mask = need - 1, cur = 0, count = 0;
    for (int i = 0; i < (int)s.size(); i++) {
        cur = ((cur << 1) | (s[i] - '0')) & mask;
        if (i >= k - 1 && !seen[cur]) {
            seen[cur] = true;
            if (++count == need) return true;
        }
    }
    return false;
}

JavaScript

var hasAllCodes = function(s, k) {
    var need = 1 << k;
    if (s.length - k + 1 < need) return false;
    var seen = new Uint8Array(need);
    var mask = need - 1, cur = 0, count = 0;
    for (var i = 0; i < s.length; i++) {
        cur = ((cur << 1) | (s.charCodeAt(i) - 48)) & mask;
        if (i >= k - 1 && seen[cur] === 0) {
            seen[cur] = 1;
            count++;
            if (count === need) return true;
        }
    }
    return false;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Hashing: Hash Maps and Hash Sets