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.
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; }}Video 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.