Check If a String Contains All Binary Codes of Size K - Video Solutions
Check if a String Contains all Binary Codes of Size K - Leetcode 1461 - Python
Check If a String Contains All Binary Codes of Size K - Video Solution
Watch 10 video solutions for Check If a String Contains All Binary Codes of Size K, a medium level problem involving Hash Table, String, Bit Manipulation. This walkthrough by NeetCode has 20,412 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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
Approach Overview
Problem 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.
Complexity Analysis
| 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 |