Check If a String Contains All Binary Codes of Size K
MedPrompt
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
Approaches
3 approaches with complexity analysis and trade-offs.
This approach is a straightforward brute-force method. It works by first generating every possible binary code of length k. Then, for each of these 2^k codes, it performs a search within the input string s to check for its presence. While simple to conceptualize, its performance is very poor due to the nested operations of generation and searching.
Algorithm
- Calculate the total number of required codes, which is
2^k. - Iterate through all numbers from
0to2^k - 1. - For each number, convert it to its
k-bit binary string representation. This may require padding with leading zeros. - For each generated binary string, check if it exists as a substring within the input string
s. - If any binary code is not found in
s, we can immediately conclude that not all codes are present and returnfalse. - If the loop completes without finding any missing codes, it means all
2^kcodes were found, and we returntrue.
Walkthrough
The core idea is to exhaustively check for every single possibility. We know there are 2^k unique binary codes of length k. We can generate them by iterating from integer 0 to 2^k - 1 and converting each integer to its binary string form, ensuring each string is padded with leading zeros to have a length of exactly k. For example, if k=3 and i=1, we generate the string "001". After generating a code, we use a standard library function like s.contains() to search for it in the input string. If at any point a code is not found, we can stop and return false. If we successfully iterate through all 2^k codes and find each one in s, we return true.
class Solution { public boolean hasAllCodes(String s, int k) { int totalCodes = 1 << k; // This is 2^k for (int i = 0; i < totalCodes; i++) { String binaryCode = Integer.toBinaryString(i); // Create a format string like "%03s" if k=3 to pad with zeros String format = "%" + k + "s"; String paddedCode = String.format(format, binaryCode).replace(' ', '0'); if (!s.contains(paddedCode)) { return false; } } return true; }}Complexity
Time
O(2^k * N * k), where `N` is the length of `s`. We generate `2^k` codes. For each code, `s.contains()` can take up to `O(N * k)` time in the worst case. This complexity is too high for the given constraints.
Space
O(k). This space is used to temporarily store each binary code string of length `k` that is generated.
Trade-offs
Pros
Simple to understand and implement the logic.
Cons
Extremely inefficient and slow, especially for larger values of
kands.length().The time complexity makes it infeasible for the given constraints, leading to a 'Time Limit Exceeded' error.
A more practical approach is to iterate through the input string s and find all unique substrings of length k. We can use a HashSet to keep track of the substrings we've encountered. By the end of the iteration, if the number of unique substrings in our set is equal to 2^k, we know that all possible binary codes were present in the string.
Algorithm
- Create a
HashSet<String>to store unique substrings. - Calculate the total number of codes required,
requiredCount = 2^k. - Iterate through the input string
sfrom indexi = 0up tos.length() - k. - In each iteration, extract the substring of length
kstarting ati(i.e.,s.substring(i, i + k)). - Add this substring to the
HashSet. The set will automatically handle duplicates. - After the loop finishes, compare the size of the
HashSetwithrequiredCount. - If
hashSet.size() == requiredCount, it means all possible codes were found, so returntrue. Otherwise, returnfalse.
Walkthrough
Instead of generating codes and searching for them, this method reverses the process. We slide a window of size k over the string s. At each position, we extract the k-length substring and insert it into a HashSet<String>. The HashSet provides an efficient way to store only the unique substrings. After iterating through all possible starting positions in s, we are left with a set containing every unique k-length binary code that appears in s. The final step is to check if the size of this set is equal to 2^k. If it is, we have found all possible codes. This avoids the costly search operation of the brute-force method.
import java.util.HashSet;import java.util.Set; class Solution { public boolean hasAllCodes(String s, int k) { int n = s.length(); // It's impossible to have 2^k substrings if the string is too short. if (n < k) { return false; } Set<String> foundCodes = new HashSet<>(); for (int i = 0; i <= n - k; i++) { foundCodes.add(s.substring(i, i + k)); } return foundCodes.size() == (1 << k); }}Complexity
Time
O(N * k), where `N` is the length of `s`. The loop runs `N - k + 1` times. Inside the loop, `substring()` takes `O(k)` time, and adding it to the `HashSet` also takes `O(k)` on average (for hashing and equality checks).
Space
O(2^k * k). In the worst case, the `HashSet` stores `2^k` unique strings, each of length `k`.
Trade-offs
Pros
Significantly more efficient than the brute-force approach.
Relatively easy to implement and understand.
Passes the time limits for the given constraints.
Cons
Creating a new substring in each iteration can be inefficient for very long strings.
The space complexity depends on
kand can be large ifkis close to 20, as it stores2^kstrings of lengthk.
The most optimal solution uses a sliding window combined with a rolling hash. Instead of working with strings, we can represent each binary code of length k as an integer. This allows for a very fast, O(1) update of the code's value as we slide the window one position at a time. We use a boolean array or a HashSet of integers to keep track of the codes we have found, which is more memory-efficient than storing strings.
Algorithm
- Calculate
totalCodes = 2^k. Check ifs.length()is sufficient to contain all codes. Ifs.length() - k + 1 < totalCodes, returnfalse. - Create a
booleanarrayseenof sizetotalCodesinitialized tofalse. - Calculate the integer value (
hash) for the firstk-length substring ofs. - Mark this first hash as seen:
seen[hash] = true, and initialize a counterfoundCount = 1. - Use a rolling hash technique: iterate from
i = ktos.length() - 1.- Update the hash in
O(1)time: shift the previous hash left by one bit, mask it tokbits, and OR it with the new bit froms.charAt(i). - If the new hash has not been seen before (
!seen[newHash]):- Mark it as seen:
seen[newHash] = true. - Increment
foundCount.
- Mark it as seen:
- Update the hash in
- After the loop, return
trueiffoundCount == totalCodes, andfalseotherwise.
Walkthrough
This approach enhances the sliding window concept by avoiding the overhead of creating and hashing new string objects in each step. We treat each k-length binary substring as a k-bit integer. First, we compute the integer value for the initial window of k characters. Then, we iterate through the rest of the string. In each step, we efficiently calculate the integer value of the new window by using the value from the previous window. This is done by shifting the old value one bit to the left (which discards the most significant bit's old contribution), and then adding the new character's bit value as the new least significant bit. A bitmask is used to ensure the integer value stays within k bits. We use a boolean array seen of size 2^k to mark which integer codes have been encountered. If we find all 2^k codes, we return true.
class Solution { public boolean hasAllCodes(String s, int k) { int n = s.length(); int totalCodes = 1 << k; if (n < k) { return false; } boolean[] seen = new boolean[totalCodes]; int foundCount = 0; int currentHash = 0; int mask = totalCodes - 1; // A mask of k ones, e.g., k=3 -> mask=7 (111) // Calculate hash for the first window of size k for (int i = 0; i < k; i++) { currentHash = (currentHash << 1) | (s.charAt(i) - '0'); } seen[currentHash] = true; foundCount = 1; // Slide the window through the rest of the string for (int i = k; i < n; i++) { // Update hash using rolling hash technique currentHash = ((currentHash << 1) & mask) | (s.charAt(i) - '0'); if (!seen[currentHash]) { seen[currentHash] = true; foundCount++; } } return foundCount == totalCodes; }}Complexity
Time
O(N), where `N` is the length of `s`. The initial hash calculation takes `O(k)`, and the subsequent loop runs `N-k` times with `O(1)` work inside. Thus, the total time is `O(k + N - k) = O(N)`.
Space
O(2^k). We need a data structure (a boolean array in this case) to keep track of the `2^k` possible codes.
Trade-offs
Pros
Optimal time complexity, as it processes the string in a single pass.
Memory efficient, as it stores integers or booleans instead of strings.
Avoids the overhead of repeated substring creation and hashing.
Cons
The rolling hash logic is slightly more complex to implement compared to the substring approach.
Solutions
Solution
class Solution {public boolean hasAllCodes(String s, int k) { Set<String> ss = new HashSet<>(); for (int i = 0; i < s.length() - k + 1; ++i) { ss.add(s.substring(i, i + k)); } return ss.size() == 1 << k; }}class Solution {public: bool hasAllCodes(string s, int k) { unordered_set<string> ss; for (int i = 0; i + k <= s.size(); ++i) { ss.insert(move(s.substr(i, k))); } return ss.size() == 1 << k; }};class Solution: def hasAllCodes(self, s: str, k: int) -> bool: ss = {s[i: i + k] for i in range(len(s) - k + 1)} return len(ss) == 1 << kVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.