LeetCode 1461: Check All Binary Codes of Size K (O(n) Solution)

When you’re given a long binary string like 00110110, the problem LeetCode 1461 — Check If a String Contains All Binary Codes of Size K asks something very specific:

Does this string contain every possible binary substring of length k?

At first glance, it sounds like you’d have to generate all 2^k binary codes and search for each one—which would be slow. The good news is: you don’t need to generate anything. You can solve it efficiently by scanning the string once.

Problem overview

You are given:

a binary string s (only '0' and '1')
an integer k

Return True if every binary code of length k appears somewhere in s as a substring, otherwise return False.

Example

If k = 2, the required codes are:

00, 01, 10, 11 → total 2^2 = 4

If the string contains all of them at least once, the answer is True.

Key idea (the important observation)

There are exactly:

2^k different binary codes of length k

And the string s can produce at most:

n - k + 1 substrings of length k (where n = len(s))

So if:

n - k + 1 < 2^k

…it’s impossible for s to contain all binary codes. We can return False immediately.

This simple check saves time on many inputs.

Best approach: Sliding window + bitmask (rolling binary value)

Instead of slicing substrings like s[i:i+k] repeatedly (which costs extra time and memory), we treat each window of length k as a number.

How we “roll” the window

As we move from left to right:

Shift the current value left by 1 (like multiplying by 2)
Add the new bit (0 or 1)
Keep only the last k bits using a mask

That mask is:

mask = (1 << k) - 1

So the rolling update becomes:

cur = ((cur << 1) & mask) | bit

Once we’ve processed at least k characters, cur represents the current length-k substring as an integer from 0 to 2^k - 1.

We track which values have appeared. If we’ve seen all 2^k values, return True.

Correct and optimized Python solution

This version is fast, clear, and avoids confusing boolean-to-int behavior by converting bits explicitly.

class Solution:
    def hasAllCodes(self, s: str, k: int) -> bool:
        n = len(s)
        need = 1 << k  # total codes = 2^k

        # Early exit: not enough windows to cover all codes
        if n < k or (n - k + 1) < need:
            return False

        seen = [False] * need
        mask = need - 1

        cur = 0
        found = 0

        for i, ch in enumerate(s):
            bit = 1 if ch == '1' else 0
            cur = ((cur << 1) & mask) | bit

            # Start checking once window size is k
            if i >= k - 1:
                if not seen[cur]:
                    seen[cur] = True
                    found += 1
                    if found == need:
                        return True

        return False

Step-by-step example (quick walkthrough)

Let:

s = "00110110"
k = 2
need = 4 (00, 01, 10, 11)

As we slide a window of size 2, we encounter:

00 ✅
01 ✅
11 ✅
10 ✅

We found all 4 codes → return True.

Why this solution is efficient

Time complexity

O(n) — one pass through the string

Space complexity

O(2^k) — to store which binary codes we’ve seen

This is the standard optimal approach for LeetCode 1461.

Common mistakes to avoid

Building every substring with slicing (s[i:i+k]) inside a loop — slower for large inputs.
Not using a mask — without & mask, your rolling number keeps growing and stops representing only the last k bits.
Skipping the early exit check — wastes time on impossible cases.