Check If a String Contains All Binary Codes of Size K - Solution & Explanation

Q: 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.

Q: 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.

Q: 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.

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.

MediumHash Table String Bit Manipulation Rolling Hash14 min readAsked at: Amazon, Microsoft, Meta +2

Practice this problem

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 * 10⁵
s[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.

Approach 1: Bitmask with Set

This approach uses a set to store all unique substrings of length k encountered in s. By sliding a window of size k across the string, we add each substring to the set. If the set size equals 2^k, return true because all possible binary strings of length k are present. Otherwise, return false.

The function utilizes a set to keep track of unique substrings of length k. Iterating over the string from index 0 to len(s)-k, each k-length substring is added to the set. If the set's size becomes 2^k, we know all binary codes of length k are present in s. The operation seen.add(substring) ensures unique tracking, while len(seen) == 2**k quickly checks the condition to return true.

Code

Python Java JavaScript

Python

Java

JavaScript

Complexity

Time Complexity: O(n * k) where n is the length of the string,
Space Complexity: O(min(2^k, n)), primarily due to the set storing at most 2^k elements.

Try this approach in the editor →

Approach 2: Sliding Window with Bitmask

This approach improves efficiency by using bit manipulation instead of storing full substrings. Treat the k-length binary strings as numbers and update a rolling number using bitmasking while sliding over string s. This can detect all variations without explicitly storing them.

The C solution utilizes a boolean array to represent the presence of each binary code of length k. By treating binary codes as integers and updating a rolling hash (a bitmask method shifting left and masking), it determines uniqueness with minimal space. Each k-length sequence is translated into this integer representation, tracked via the boolean array.

Code

C C++C#

C++

Complexity

Time Complexity: O(n),
Space Complexity: O(2^k), primarily determined by the boolean tracking array.

Try this approach in the editor →

Approach 3: Hash Table

First, for a string s of length n, the number of substrings of length k is n - k + 1. If n - k + 1 < 2^k, then there must exist a binary string of length k that is not a substring of s, so we return false.

Next, we traverse the string s and store all substrings of length k in a set ss. Finally, we check if the size of the set ss is equal to 2^k.

The time complexity is O(n times k), and the space complexity is O(n). Here, n is the length of the string s.

Code

Python Java C++Go TypeScript

Python

Java

C++

TypeScript

Try this approach in the editor →

Approach 4: Sliding Window

In Solution 1, we stored all distinct substrings of length k, and processing each substring requires O(k) time. We can instead use a sliding window, where each time we add the latest character, we remove the leftmost character from the window. During this process, we use an integer x to store the substring.

The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the string s.

Code

Python Java C++Go TypeScript

Python

Java

C++

TypeScript

Try this approach in the editor →

Complexity Comparison

Approach	Complexity
Bitmask with Set	Time Complexity: O(n * k) where n is the length of the string, Space Complexity: O(min(2^k, n)), primarily due to the set storing at most 2^k elements.
Sliding Window with Bitmask	Time Complexity: O(n), Space Complexity: O(2^k), primarily determined by the boolean tracking array.
Hash Table	—
Sliding Window	—

Detailed 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

Video Solution

Check if a String Contains all Binary Codes of Size K - Leetcode 1461 - Python • NeetCode • 20,412 views views

Watch 9 more video solutions →

Frequently Asked Questions

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.

Ready to solve this problem?

Practice Check If a String Contains All Binary Codes of Size K with our built-in code editor and test cases.

Practice on FleetCode

Two Sum

Longest Substring Without Repeating Characters

Problem Info

DifficultyMedium

Acceptance61.5%

Approaches4

Reading time14 min

Asked at

Amazon Microsoft Meta Google Grammarly

Practice this problem

Open in Editor

Problem Statement

Approach Overview

Approach 1: Bitmask with Set

Code

Complexity

Approach 2: Sliding Window with Bitmask

Code

Complexity

Approach 3: Hash Table

Code

Approach 4: Sliding Window

Code

Complexity Comparison

Detailed Complexity Analysis

Video Solution

Frequently Asked Questions

Related Problems

Ready to solve this problem?

Problem Info

Table of Contents