Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

There are exactly 2^k different binary strings of length k. Every length-k substring belongs to that universe, so seeing 2^k distinct substrings proves that every possible code is present. Repeated appearances of one code do not help.

Approach

Insert every length-k sliding substring into a set, then compare the set's size with 2^k. Return whether they match. These implementations materialize the substrings rather than maintaining a rolling integer encoding. If k exceeds the input length, no window is inserted and the answer is false.

class Solution:
    def hasAllCodes(self, s: str, k: int) -> bool:
        n = len(s)
        codes = set()

        for i in range(n - k + 1):
            codes.add(s[i: i + k])

        if len(codes) == 2**k:
            return True
        return False

Complexity analysis

Let n = s.length and W = max(0, n - k + 1). Creating and hashing W length-k substrings costs O(W*k) time, plus constant setup under the bounded k constraint. The set stores at most min(W, 2^k) strings, using O(min(W, 2^k)*k) auxiliary character storage. If k > n, the loop is empty and both time and working space are constant.