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

Difficulty: Medium | Pattern: Hash Set / Sliding Window | Company tags: Amazon, Shopee

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: Binary codes of length 2: "00","01","10","11". All appear as substrings.

Example 2:

Input: s = "0110", k = 2
Output: false
Explanation: "11" is not a substring.

Example 3:

Input: s = "0110", k = 1
Output: true  ("0" and "1" both appear)

Approach: Sliding Window Hash Set — O(n×k)

Key insight: There are exactly 2^k binary codes of length k. Slide a window of size k over s, add each substring to a set. If the set size reaches 2^k, all codes exist.

def hasAllCodes(s: str, k: int) -> bool:
    needed = 1 << k  # 2^k
    if len(s) < k + needed - 1:  # impossible if string too short
        return False
    
    seen = set()
    for i in range(len(s) - k + 1):
        seen.add(s[i:i+k])
        if len(seen) == needed:
            return True
    
    return False

Optimized: Rolling Hash — O(n)

def hasAllCodes(s: str, k: int) -> bool:
    needed = 1 << k
    seen = set()
    cur = int(s[:k], 2)
    seen.add(cur)
    mask = needed - 1  # k ones: 0b111...1
    
    for i in range(k, len(s)):
        cur = ((cur << 1) & mask) | int(s[i])
        seen.add(cur)
    
    return len(seen) == needed

Rolling hash: shift left, mask to k bits, OR with new bit.

Algorithm Flow

Dry Run

s = "00110110", k=2, needed=4

i	substring	seen size
0	"00"	1
1	"01"	2
2	"11"	3
3	"10"	4 = needed ✓
len=4=needed ✓

Return True ✓

Edge Cases

• k=1 → need both "0" and "1"
• len(s) < 2^k + k - 1 → impossible, return False early
• All same bit → only 1 unique code found, never reaches 2^k

Complexity

Approach	Time	Space
Sliding window (set)	O(n×k)	O(k × 2^k)
Rolling hash	O(n)	O(2^k)

Key Terms

Term	Definition
Sliding window	Fixed-size window of length k moved one character at a time across the string, avoiding redundant re-scans.
Rolling bitmask	Integer representation of the current k-length window, updated via (cur << 1) & mask | newBit instead of re-parsing the substring.
Bitmask mask = 2^k - 1	k ones used to discard bits that fall outside the current window when shifting.
Hash set	Collection of already-seen codes (as strings or integers) used to count distinct codes without duplicates.
Pigeonhole bound	len(s) < k + 2^k - 1 guarantees not enough window positions exist to cover all codes, allowing early exit.

FAQ

Q: Can this be solved without extra space (O(1))? A: Not in general — you need to track which of the 2^k codes have been seen, which inherently requires O(2^k) space (a set, bit-vector, or boolean array). A bit-vector of size 2^k is the most compact form but still O(2^k).

Q: What if k is larger than the string length? A: Then no window of size k fits, so return False immediately. This is also covered by the pigeonhole check len(s) < k.

Q: Why use an integer bitmask instead of string slicing? A: String slicing creates a new O(k) string each step, giving O(n×k) time. The rolling bitmask updates in O(1) per step using shift/mask/OR, giving O(n) overall — critical when k is large (up to ~20 per constraints, since 2^20 codes is already a million).

Q: How would this change if the alphabet were not binary (e.g., DNA bases A/C/G/T)? A: You'd use a base-4 (or size-of-alphabet) rolling hash instead of a bitmask: cur = cur * base + digit(s[i]), then mod by base^k to drop the oldest character. This is exactly the technique used in Repeated DNA Sequences-style problems.

Q: What's the early-exit optimization and why does it matter? A: Return True as soon as len(seen) == 2^k, without scanning the rest of the string. In the best case (all codes found early) this avoids unnecessary work, though worst-case time remains O(n).

Quick Revision

• Goal: check whether all 2^k binary strings of length k appear as substrings of s.
• There are exactly 2^k distinct codes of length k — this is the target count.
• Slide a window of size k across s, collecting each window into a set.
• Naive approach: substring + set → O(n×k) time, O(k·2^k) space.
• Optimized approach: maintain a rolling integer bitmask instead of a substring.
• Update rule: cur = ((cur << 1) & mask) | newBit, where mask = 2^k - 1.
• Track seen integers in a set (or boolean array of size 2^k); compare final size to 2^k.
• Early exit: return True the moment len(seen) == 2^k.
• Edge case: if len(s) < k + 2^k - 1, not enough windows exist — return False without scanning.
• Time: O(n) with rolling hash; Space: O(2^k) for the seen set.

Related Problems

• Same rolling-hash-over-fixed-window pattern (base-4 alphabet instead of binary): named as "Repeated DNA Sequences" pattern (LeetCode 187) — file not present in this directory.
• 3-LongestSubstringWithoutRepeatingCharacters.md — classic variable-size sliding window with a hash set/map tracking window contents.
• 718-MaximumLengthOfRepeatedSubarray.md — shares the "compare fixed-length windows across a sequence" theme, solved with DP instead of hashing.