Check If a String Contains All Binary Codes of Size K solution and explanation
Google
9 more videos on this problem
Check if a String Contains all Binary Codes of Size K - Leetcode 1461 - PythonNeetCode · 5:42 · 20K views
Leetcode 1461. Check If a String Contains All Binary Codes of Size KCode with Alisha · 11:20 · 2K views
LeetCode 1461 Check If a String Contains All Binary Codes of Size KNaresh Gupta · 5:56 · 1K views
Check If a String Contains All Binary Codes of Size K | Leetcode 1461Coding Decoded · 9:22 · 1K views
LeetCode 1461. Check If a String Contains All Binary Codes of Size KHappy Coding · 12:43 · 515 views
1461. Check If a String Contains All Binary Codes of Size K | Leetcode Daily - PythonLeetcode Daily · 7:16 · 386 views
Daily Leetcode #2155: Feb 23, 2026 - 1461. Check If a String Contains All Binary Codes of Size KProgramming Live with Larry · 3:46 · 369 views
Leetcode - Check If a String Contains All Binary Codes of Size K (Python)Timothy H Chang · 4:00 · 361 views
Check If a String Contains All Binary Codes of Size K | LeetCode 1461 | Java Code | Developer CoderDeveloper Coder · 8:06 · 323 views
Check If a String Contains All Binary Codes of Size K (Leetcode 1461)Coding Interviews · 18:59 · 248 views
The 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.
Example 1:
Input: s = "00110110", k = 2 Output: true Explanation: The binary codes of length 2 are "00", "01", "10" and "11". They can be all found as substrings at indices 0, 1, 3 and 2 respectively.
Example 2:
Input: s = "0110", k = 1 Output: true Explanation: The binary codes of length 1 are "0" and "1", it is clear that both exist as a substring.
Example 3:
Input: s = "0110", k = 2 Output: false Explanation: The binary code "00" is of length 2 and does not exist in the array.
Constraints:
1 <= s.length <= 5 * 105s[i]is either'0'or'1'.1 <= k <= 20
Approach overview
Problem Overview: Given a binary string s and an integer k, determine whether every possible binary code of length k appears as a substring. Since there are exactly 2^k different binary codes of size k, the goal is to scan the string and confirm that all of them occur at least once.
Approach 1: Bitmask with Set (O(n) time, O(2^k) space)
Iterate through the string and extract every substring of length k. Each substring represents a binary number, so convert it to an integer using bit manipulation and insert it into a hash set. The key idea is that if the set size becomes 2^k, you have seen every possible binary code. This approach relies on fast membership checks provided by a hash table. Time complexity is O(n) for scanning substrings, while space complexity is O(2^k) to store distinct codes.
Approach 2: Sliding Window with Bitmask (O(n) time, O(2^k) space)
A more efficient implementation avoids repeatedly converting substrings. Maintain a rolling integer bitmask representing the last k bits. As you iterate through the string, left shift the current mask, add the new bit, and remove the oldest bit using a mask like (1 << k) - 1. This technique is essentially a lightweight rolling hash. Track seen masks using a boolean array or set. Each step updates the window in constant time, producing an overall O(n) time complexity with O(2^k) memory.
The sliding window works because every substring of length k can be represented by its integer bit pattern. Updating the mask with bit operations eliminates substring extraction and parsing overhead.
Recommended for interviews: The sliding window with bitmask is the approach most interviewers expect. It demonstrates understanding of bit manipulation, rolling windows, and how to encode binary substrings efficiently. The set-based method is still valuable because it clearly expresses the idea of collecting unique substrings. Start there if explaining the intuition, then optimize using the rolling bitmask.
Approach 1: Bitmask with Set
This approach uses a set to store all unique substrings of length k encountered in s. By sliding a window of size k across the string, we add each substring to the set. If the set size equals 2^k, return true because all possible binary strings of length k are present. Otherwise, return false.
def hasAllCodes(s: str, k: int) -> bool:
seen = set()
for i in range(len(s) - k + 1):
substring = s[i:i+k]
seen.add(substring)
if len(seen) == 2**k:
return True
return False
import java.util.HashSet;
public class Solution {
public boolean hasAllCodes(String s, int k) {
HashSet<String> seen = new HashSet<>();
for (int i = 0; i <= s.length() - k; i++) {
String sub = s.substring(i, i + k);
seen.add(sub);
if (seen.size() == (1 << k)) {
return true;
}
}
return false;
}
}
function hasAllCodes(s, k) {
const seen = new Set();
for (let i = 0; i <= s.length - k; i++) {
const substring = s.substring(i, i + k);
seen.add(substring);
if (seen.size === 2 ** k) {
return true;
}
}
return false;
}The function utilizes a set to keep track of unique substrings of length k. Iterating over the string from index 0 to len(s)-k, each k-length substring is added to the set. If the set's size becomes 2^k, we know all binary codes of length k are present in s. The operation seen.add(substring) ensures unique tracking, while len(seen) == 2**k quickly checks the condition to return true.
Time Complexity: O(n * k) where n is the length of the string,
Space Complexity: O(min(2^k, n)), primarily due to the set storing at most 2^k elements.
Approach 2: Sliding Window with Bitmask
This approach improves efficiency by using bit manipulation instead of storing full substrings. Treat the k-length binary strings as numbers and update a rolling number using bitmasking while sliding over string s. This can detect all variations without explicitly storing them.
#include <vector>
#include <string>
class Solution {
public:
bool hasAllCodes(std::string s, int k) {
int need = 1 << k;
std::vector<bool> seen(need, false);
int hash = 0;
int allOnes = need - 1;
for (int i = 0; i < s.size(); i++) {
hash = ((hash << 1) & allOnes) | (s[i] - '0');
if (i >= k - 1 && !seen[hash]) {
seen[hash] = true;
if (--need == 0) return true;
}
}
return false;
}
};
#include <stdbool.h>
#include <string.h>
bool hasAllCodes(char * s, int k) {
int need = 1 << k;
bool seen[need];
memset(seen, false, sizeof(seen));
int hash = 0;
int allOnes = need - 1;
for (int i = 0; s[i]; i++) {
hash = ((hash << 1) & allOnes) | (s[i] - '0');
if (i >= k - 1 && !seen[hash]) {
seen[hash] = true;
if (--need == 0) return true;
}
}
return false;
}
using System;
public class Solution {
public bool HasAllCodes(string s, int k) {
int need = 1 << k;
bool[] seen = new bool[need];
int hash = 0;
int allOnes = need - 1;
for (int i = 0; i < s.Length; i++) {
hash = ((hash << 1) & allOnes) | (s[i] - '0');
if (i >= k - 1 && !seen[hash]) {
seen[hash] = true;
if (--need == 0) return true;
}
}
return false;
}
}This C++ approach involves a boolean vector to mark seen k-length binary sequences as integers. Bit manipulation (shifts and masks) facilitates efficient updating of the hash representing these substrings. As each is checked and marked, the solution recognizes when all possible sequences have been seen.
Time Complexity: O(n),
Space Complexity: O(2^k), owing to the boolean vector for tracking sequences.
Approach 3: Hash Table
First, for a string s of length n, the number of substrings of length k is n - k + 1. If n - k + 1 < 2^k, then there must exist a binary string of length k that is not a substring of s, so we return false.
Next, we traverse the string s and store all substrings of length k in a set ss. Finally, we check if the size of the set ss is equal to 2^k.
The time complexity is O(n times k), and the space complexity is O(n). Here, n is the length of the string s.
function hasAllCodes(s: string, k: number): boolean {
const n = s.length;
const m = 1 << k;
if (n - k + 1 < m) {
return false;
}
const ss = new Set<string>();
for (let i = 0; i + k <= n; ++i) {
ss.add(s.slice(i, i + k));
}
return ss.size === m;
}func hasAllCodes(s string, k int) bool {
n, m := len(s), 1<<k
if n-k+1 < m {
return false
}
ss := map[string]bool{}
for i := 0; i+k <= n; i++ {
ss[s[i:i+k]] = true
}
return len(ss) == m
}Approach 4: Sliding Window
In Solution 1, we stored all distinct substrings of length k, and processing each substring requires O(k) time. We can instead use a sliding window, where each time we add the latest character, we remove the leftmost character from the window. During this process, we use an integer x to store the substring.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the string s.
function hasAllCodes(s: string, k: number): boolean {
const n = s.length;
const m = 1 << k;
if (n - k + 1 < m) {
return false;
}
let x = +`0b${s.slice(0, k)}`;
const ss = new Set<number>();
ss.add(x);
for (let i = k; i < n; ++i) {
const a = +s[i - k] << (k - 1);
const b = +s[i];
x = ((x - a) << 1) | b;
ss.add(x);
}
return ss.size === m;
}func hasAllCodes(s string, k int) bool {
n, m := len(s), 1<<k
if n-k+1 < m {
return false
}
ss := make([]bool, m)
x, _ := strconv.ParseInt(s[:k], 2, 64)
ss[x] = true
for i := k; i < n; i++ {
a := int64(s[i-k]-'0') << (k - 1)
b := int64(s[i] - '0')
x = (x-a)<<1 | b
ss[x] = true
}
for _, v := range ss {
if !v {
return false
}
}
return true
}Complexity comparison
| Approach | Complexity |
|---|---|
| Bitmask with Set | Time Complexity: O(n * k) where n is the length of the string, |
| Sliding Window with Bitmask | Time Complexity: O(n), |
| Hash Table | – |
| Sliding Window | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Bitmask with Set | O(n) | O(2^k) | Good for clarity and quick implementation when converting substrings to integers is acceptable |
| Sliding Window with Bitmask | O(n) | O(2^k) | Preferred in interviews and large inputs since it avoids substring extraction and uses rolling bit operations |
Frequently asked questions
Is Check If a String Contains All Binary Codes of Size K easy or hard?
This problem is generally rated Medium difficulty. The brute-force idea of collecting all length-k substrings is simple, but the optimized solution requires understanding sliding windows and bit manipulation to efficiently encode binary substrings.
Check If a String Contains All Binary Codes of Size K Python/Java solution
Python and Java implementations usually track seen binary patterns using a set or boolean array. The algorithm iterates through the string, updates a rolling k-bit mask with bit operations, and counts unique masks until reaching 2^k. This keeps runtime linear with respect to the string length.
How to solve Check If a String Contains All Binary Codes of Size K in O(n)?
Use a sliding window with a k-bit rolling mask. Shift the mask left, add the current bit, and remove older bits using (1 << k) - 1. Each mask value represents a substring of length k, so mark it as seen in a set or boolean array. When the number of unique masks reaches 2^k, every binary code exists in the string.
What is the best approach for Check If a String Contains All Binary Codes of Size K?
The sliding window with bitmask approach is the most efficient and commonly expected solution. It maintains a rolling integer representing the last k bits while scanning the string once. Each update uses bit shifts and masking, giving O(n) time complexity and O(2^k) space to track which binary codes have appeared.
Is Check If a String Contains All Binary Codes of Size K asked at Google/Amazon/Meta?
Binary substring and bitmask-based sliding window problems appear frequently in interviews at companies like Google, Amazon, and Meta. This problem tests string processing, hash-based deduplication, and efficient bit manipulation techniques commonly expected in mid-level algorithm interviews.
What data structure is used in Check If a String Contains All Binary Codes of Size K?
The solution typically uses a hash set or a boolean array to record which binary codes have appeared. Combined with a rolling bitmask, this allows constant-time checks and efficient tracking of up to 2^k possible codes.
What is the time complexity of Check If a String Contains All Binary Codes of Size K?
The optimal solution runs in O(n) time where n is the length of the string. Each character is processed once while maintaining a rolling k-bit mask. The algorithm also uses O(2^k) space to track all possible binary codes of length k.