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 <= 20In #1461 Check If a String Contains All Binary Codes of Size K, the goal is to determine whether every possible binary substring of length k exists within the given string. Since there are 2^k possible binary codes, the problem becomes one of efficiently tracking all unique substrings of size k.
A common strategy is to use a sliding window combined with a hash set. As the window moves across the string, each substring of length k is recorded. If the number of unique substrings reaches 2^k, all possible codes are present. To further optimize, a rolling hash or bitmask technique can be used to convert each window into an integer representation, allowing constant-time updates while sliding the window.
This avoids repeatedly constructing substrings and reduces overhead. The algorithm processes the string in a single pass, making it efficient for large inputs while ensuring each possible code is checked.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Sliding Window with Hash Set | O(n * k) | O(2^k) |
| Rolling Hash / Bitmask Optimization | O(n) | O(2^k) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
We need only to check all sub-strings of length k.
The number of distinct sub-strings should be exactly 2^k.
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.
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.
1
2 function hasAllCodes(s, k) {
3 const seen = new Set();
4 for (let i = 0; i <= s.length - k; i++) {
5 const substring = s.substring(i, i + k);
6 seen.add(substring);
7 if (seen.size === 2 ** k) {
8 return true;
9 }
10 }
11 return false;
12 }
13 This function uses a Set in JavaScript to handle unique substrings. By extracting substrings via s.substring(i, i + k), we add each to our set. Thus, it checks seen.size === 2 ** k to determine if all possible codes are present, promptly returning true in that scenario.
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.
Time Complexity: O(n),
Space Complexity: O(2^k), primarily determined by the boolean tracking array.
1
2 #include <vector>
3 #include <string>
4
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;
}
};
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
For a binary string of length k, there are exactly 2^k possible unique combinations. If the number of distinct substrings of length k in the input string equals 2^k, it guarantees that all binary codes are present.
Yes, this type of problem is common in technical interviews because it tests sliding window techniques, hashing, and bit manipulation. Companies often use it to evaluate a candidate's ability to optimize substring checks.
A hash set or a boolean array is typically used to track which binary codes have appeared. When using a rolling hash or bitmask, a boolean array of size 2^k can efficiently mark visited patterns.
The optimal approach uses a sliding window combined with a rolling hash or bitmask. Each k-length substring is converted into an integer representation and tracked in a set or boolean array. This allows checking all substrings in linear time.
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.