NeetCode #128LC-1461MediumArrays & Hashing
← Back to All Problems#128 · #1461 · Check If a String Contains All Binary Codes of Size K(检查一个字符串是否包含所有长度为 K 的二进制子串)
📌 Problem Statement & Constraints
Given a binary string
s and an integer k, return true if every binary code of length k appears as a substring of s. Constraints: 1 <= s.length <= 5 * 10^5, 1 <= k <= 20.💡 Core Algorithmic Approaches
- There are exactly
2^kdistinct binary strings of lengthk. - Collect all substrings of length
kinto a set and check whether its size equals2^k. - The bound
k <= 20keeps2^kat about a million, which is manageable. - A necessary condition is
len(s) >= 2^k + k - 1, since that is the minimum length of a de Bruijn sequence containing every code -- a useful early exit.
💻 Benchmark Python3 Implementation
class Solution:
def hasAllCodes(self, s: str, k: int) -> bool:
if len(s) < k:
return False
seen = {s[i:i + k] for i in range(len(s) - k + 1)}
return len(seen) == (1 << k) # 2^k distinct codes needed
# Early-exit variant: the theoretical minimum length rules out many inputs at once
class Solution2:
def hasAllCodes(self, s: str, k: int) -> bool:
if len(s) < (1 << k) + k - 1: # de Bruijn lower bound
return False
seen = {s[i:i + k] for i in range(len(s) - k + 1)}
return len(seen) == (1 << k)⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n * k) with the direct set construction (each substring slice costs O(k)), or O(n) with a rolling integer hash. The early-exit variant often returns in O(1).
💾 Space Complexity
O(2^k) for the set of codes, which is at most about a million entries.
⚠️ Interview Pitfalls & Follow-ups
- Using
range(len(s) - k): the last substring is missed; the bound islen(s) - k + 1. - Checking
len(seen) >= 2^k: it can never exceed2^k, so==is the right test (and>=would be equivalent but misleading). - Forgetting the
len(s) < kguard: the slice range would be empty and the set would be empty, so it would returnFalseanyway -- but the guard makes the intent explicit. - Assuming
kcan be large:k <= 20is what makes enumerating all2^kcodes feasible.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.