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.
- Difficulty: Medium
- Topics: Strings, Hash Table, Bit Manipulation, Rolling Hash
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
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^5s[i] is '0' or '1'1 <= k <= 20
Hints for Check If a String Contains All Binary Codes of Size K
Hint 1
shas onlyn − k + 1substrings of lengthk; if that is fewer than2^k, the answer isfalseat once.Hint 2
Collect the distinct length-
kwindows and compare their number with2^k.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 tokbits.
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
- Let
need = 2^k. Ifn − k + 1 < need, returnfalse. - Keep
cur, the value of the lastkbits read, and a boolean arrayseenof sizeneed. - For each bit, set
cur = ((cur << 1) | bit) & (need − 1); once at leastkbits have been read, markseen[cur]and count it if it was new. - Return
trueas soon as the count reachesneed, orfalseat 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
kbits have been read marks codes that do not exist. kmay exceedn— 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)}) == needJava
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