Is Check If a String Contains All Binary Codes of Size K easy or hard?

This problem is generally rated Medium difficulty. The brute-force idea of collecting all length-k substrings is simple, but the optimized solution requires understanding sliding windows and bit manipulation to efficiently encode binary substrings.

Check If a String Contains All Binary Codes of Size K Python/Java solution

Python and Java implementations usually track seen binary patterns using a set or boolean array. The algorithm iterates through the string, updates a rolling k-bit mask with bit operations, and counts unique masks until reaching 2^k. This keeps runtime linear with respect to the string length.

How to solve Check If a String Contains All Binary Codes of Size K in O(n)?

Use a sliding window with a k-bit rolling mask. Shift the mask left, add the current bit, and remove older bits using (1 << k) - 1. Each mask value represents a substring of length k, so mark it as seen in a set or boolean array. When the number of unique masks reaches 2^k, every binary code exists in the string.

What is the best approach for Check If a String Contains All Binary Codes of Size K?

The sliding window with bitmask approach is the most efficient and commonly expected solution. It maintains a rolling integer representing the last k bits while scanning the string once. Each update uses bit shifts and masking, giving O(n) time complexity and O(2^k) space to track which binary codes have appeared.

Is Check If a String Contains All Binary Codes of Size K asked at Google/Amazon/Meta?

Binary substring and bitmask-based sliding window problems appear frequently in interviews at companies like Google, Amazon, and Meta. This problem tests string processing, hash-based deduplication, and efficient bit manipulation techniques commonly expected in mid-level algorithm interviews.

What data structure is used in Check If a String Contains All Binary Codes of Size K?

The solution typically uses a hash set or a boolean array to record which binary codes have appeared. Combined with a rolling bitmask, this allows constant-time checks and efficient tracking of up to 2^k possible codes.

What is the time complexity of Check If a String Contains All Binary Codes of Size K?

The optimal solution runs in O(n) time where n is the length of the string. Each character is processed once while maintaining a rolling k-bit mask. The algorithm also uses O(2^k) space to track all possible binary codes of length k.

Description Hints 2 Solution Video 5:42

1461. Check If a String Contains All Binary Codes of Size K

Q: What is the best approach for Check If a String Contains All Binary Codes of Size K?

The sliding window with bitmask approach is the most efficient and commonly expected solution. It maintains a rolling integer representing the last k bits while scanning the string once. Each update uses bit shifts and masking, giving O(n) time complexity and O(2^k) space to track which binary codes have appeared.

Q: Is Check If a String Contains All Binary Codes of Size K asked at Google/Amazon/Meta?

Binary substring and bitmask-based sliding window problems appear frequently in interviews at companies like Google, Amazon, and Meta. This problem tests string processing, hash-based deduplication, and efficient bit manipulation techniques commonly expected in mid-level algorithm interviews.

Q: What data structure is used in Check If a String Contains All Binary Codes of Size K?

The solution typically uses a hash set or a boolean array to record which binary codes have appeared. Combined with a rolling bitmask, this allows constant-time checks and efficient tracking of up to 2^k possible codes.

Q: What is the time complexity of Check If a String Contains All Binary Codes of Size K?

The optimal solution runs in O(n) time where n is the length of the string. Each character is processed once while maintaining a rolling k-bit mask. The algorithm also uses O(2^k) space to track all possible binary codes of length k.

Medium61.5% acceptance5 companies

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 * 10⁵
s[i] is either '0' or '1'.
1 <= k <= 20

Asked at 5 companies

Grammarly

Google Amazon Microsoft Meta

Topics

Hints open one at a time

Hint 1

We need only to check all sub-strings of length k.

Hint 2

The number of distinct sub-strings should be exactly 2^k.

5:42

Still stuck?Read 4 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def hasAllCodes(self, s: str, k: int) -> bool:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

"00110110"
2

Input

"0110"
1

Input

"0110"
2

Your code is saved on this device.Solution