This problem requires verifying that all $2^k$ possible binary codes of length k appear in s as substrings. By sliding a window of length k and recording each code in a hash set, we can efficiently track which codes exist. If the hash set reaches size $2^k$, return true; otherwise, false, ensuring correctness with minimal traversal and memory.
Problem Statement
Given a binary string s and an integer k, determine whether every binary code of length k appears as a substring in s. Return true if all codes are present; otherwise, return false. This problem tests your ability to combine string manipulation with hash-based tracking efficiently.
For example, if s = "00110110" and k = 2, all binary codes of length 2 ("00", "01", "10", "11") must appear somewhere in s. You need to identify a method that can handle large strings while keeping track of all required substrings.
Examples
Example 1
Input: s = "00110110", k = 2
Output: true
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
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
The binary code "00" is of length 2 and does not exist in the array.
Constraints
- 1 <= s.length <= 5 * 105
- s[i] is either '0' or '1'.
- 1 <= k <= 20
Solution Approach
Use a Hash Set to Track Substrings
Slide a window of length k across the string s and insert each substring into a hash set. After processing, compare the hash set size to 2^k to determine if all codes exist.
Optimize with Rolling Hash
Instead of storing strings, compute an integer hash for each substring using bit manipulation. Shift bits to include the next character and mask to maintain k-length, reducing memory and improving lookup efficiency.
Early Termination for Efficiency
Track the hash set size while iterating. If it reaches 2^k before the end of s, immediately return true. This prevents unnecessary traversal when all codes are already found.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | Depends on the final approach |
| Space | Depends on the final approach |
Time complexity is O(n) because each character is processed once in the sliding window. Space complexity is O(2^k) for storing unique binary codes, which is efficient for k <= 20. Rolling hash reduces overhead compared to storing substrings directly.
What Interviewers Usually Probe
- Consider using a hash set instead of nested loops for substring existence checks.
- Notice that only substrings of length k matter; extra characters outside windows are irrelevant.
- Think about how bit manipulation can represent substrings compactly.
Common Pitfalls or Variants
Common pitfalls
- Forgetting to handle k > length of s, which should immediately return false.
- Recomputing substrings instead of using a rolling window, causing TLE on large strings.
- Incorrectly counting duplicates instead of unique substrings when verifying all codes.
Follow-up variants
- Check if a string contains all ternary codes of size k with characters '0', '1', '2'.
- Return the first missing binary code of length k if not all exist in s.
- Count how many binary codes of size k are present in s instead of a boolean check.
How GhostInterview Helps
- Automatically highlights the substring sliding window and hash set pattern for this problem.
- Detects potential failure modes like missing duplicates or exceeding memory for large k.
- Provides example-driven verification to quickly confirm correctness on edge cases.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
FAQ
What is the best approach to check all binary codes of size k in a string?
Use a sliding window of length k and a hash set or rolling hash to track all unique substrings efficiently.
Why does a rolling hash help in this problem?
Rolling hash converts substrings to integers, allowing fast updates and smaller memory footprint compared to storing strings.
What should I do if k is larger than the string length?
Immediately return false, because it is impossible for all binary codes of length k to exist in a shorter string.
Can this problem be solved without extra space?
Not fully; you need at least O(2^k) space to track which codes have appeared, but rolling hash minimizes string storage overhead.
How does this problem relate to Hash Table plus String pattern?
It combines substring tracking (String) with hash-based storage (Hash Table) to efficiently verify the presence of all binary codes.
Need direct help with Check If a String Contains All Binary Codes of Size K instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Check If a String Contains All Binary Codes of Size K from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Solve Repeated DNA Sequences by sliding a length-10 window and tracking seen patterns with a hash set or bitmask.
Open problem page#1525 Number of Good Ways to Split a StringCount all valid splits of a string where left and right substrings have equal distinct characters, using efficient state transitions.
Open problem page#1392 Longest Happy PrefixFind the longest non-empty prefix of a string that also appears as its suffix, optimizing with rolling hash techniques.
Open problem page