#1461

Medium

LeetCode Problem Workspace

Check If a String Contains All Binary Codes of Size K

Determine if every possible binary string of length k exists as a substring within a given binary string s efficiently using a hash set.

hash table string bit manipulation rolling hash hash function

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.

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.

terminal

Solution

Solution 1: 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`.

1

2

3

4

5

6

7

8

class Solution:
    def hasAllCodes(self, s: str, k: int) -> bool:
        n = len(s)
        m = 1 << k
        if n - k + 1 < m:
            return False
        ss = {s[i : i + k] for i in range(n - k + 1)}
        return len(ss) == m

Solution 2: 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.

1

2

3

4

5

6

7

8

class Solution:
    def hasAllCodes(self, s: str, k: int) -> bool:
        n = len(s)
        m = 1 << k
        if n - k + 1 < m:
            return False
        ss = {s[i : i + k] for i in range(n - k + 1)}
        return len(ss) == m

Continue Practicing

#187 repeated dna sequences #1525 number of good ways to split a string #1392 longest happy prefix