⚡Flashcard Drill➔
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

  1. There are exactly 2^k distinct binary strings of length k.
  2. Collect all substrings of length k into a set and check whether its size equals 2^k.
  3. The bound k <= 20 keeps 2^k at about a million, which is manageable.
  4. 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 is len(s) - k + 1.
  • Checking len(seen) >= 2^k: it can never exceed 2^k, so == is the right test (and >= would be equivalent but misleading).
  • Forgetting the len(s) < k guard: the slice range would be empty and the set would be empty, so it would return False anyway -- but the guard makes the intent explicit.
  • Assuming k can be large: k <= 20 is what makes enumerating all 2^k codes feasible.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Arrays & Hashing Problems