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 <= 20Problem 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.
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.
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.
Python
Java
JavaScript
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.
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.
The C solution utilizes a boolean array to represent the presence of each binary code of length k. By treating binary codes as integers and updating a rolling hash (a bitmask method shifting left and masking), it determines uniqueness with minimal space. Each k-length sequence is translated into this integer representation, tracked via the boolean array.
Time Complexity: O(n),
Space Complexity: O(2^k), primarily determined by the boolean tracking array.
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.
Python
Java
C++
Go
TypeScript
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.
Python
Java
C++
Go
TypeScript
| 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 | — |
| 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 |
Check if a String Contains all Binary Codes of Size K - Leetcode 1461 - Python • NeetCode • 20,218 views views
Watch 9 more video solutions →Practice Check If a String Contains All Binary Codes of Size K with our built-in code editor and test cases.
Practice on FleetCode