What is the best approach to check all binary codes of size k in a string?

Use a sliding window of length k and a hash set or rolling hash to track all unique substrings efficiently.

Why does a rolling hash help in this problem?

Rolling hash converts substrings to integers, allowing fast updates and smaller memory footprint compared to storing strings.

What should I do if k is larger than the string length?

Immediately return false, because it is impossible for all binary codes of length k to exist in a shorter string.

Can this problem be solved without extra space?

Not fully; you need at least O(2^k) space to track which codes have appeared, but rolling hash minimizes string storage overhead.

How does this problem relate to Hash Table plus String pattern?

It combines substring tracking (String) with hash-based storage (Hash Table) to efficiently verify the presence of all binary codes.

#1461

Medium

auto_awesome哈希·表·结合·string

LeetCode 题解工作台

检查一个字符串是否包含所有长度为 K 的二进制子串

给你一个二进制字符串 s 和一个整数 k 。如果所有长度为 k 的二进制字符串都是 s 的子串，请返回 true ，否则请返回 false 。示例 1：输入： s = "00110110", k = 2 输出： true 解释：长度为 2 的二进制串包括 "00"，"01"，"10" 和 "1…

哈希表字符串位运算滚动哈希哈希函数

题目描述

给你一个二进制字符串 s 和一个整数 k 。如果所有长度为 k 的二进制字符串都是 s 的子串，请返回 true ，否则请返回 false 。

示例 1：

输入：s = "00110110", k = 2
输出：true
解释：长度为 2 的二进制串包括 "00"，"01"，"10" 和 "11"。它们分别是 s 中下标为 0，1，3，2 开始的长度为 2 的子串。

示例 2：

输入：s = "0110", k = 1
输出：true
解释：长度为 1 的二进制串包括 "0" 和 "1"，显然它们都是 s 的子串。

示例 3：

输入：s = "0110", k = 2
输出：false
解释：长度为 2 的二进制串 "00" 没有出现在 s 中。

提示：

1 <= s.length <= 5 * 10⁵
s[i] 不是'0' 就是 '1'
1 <= k <= 20

lightbulb

解题思路

方法一：哈希表

首先，对于一个长度为 $n$ 的字符串 $s$ ，长度为 $k$ 的子串的个数为 $n - k + 1$ ，如果 $n - k + 1 < 2^k$ ，则一定存在长度为 $k$ 的二进制串不是 $s$ 的子串，返回 false。

接下来，我们遍历字符串 $s$ ，将所有长度为 $k$ 的子串存入集合 $ss$ ，最后判断集合 $ss$ 的大小是否等于 $2^k$ 。

时间复杂度 $O(n \times k)$ ，空间复杂度 $O(n)$ 。其中 $n$ 是字符串 $s$ 的长度。

1

2

3

4

5

6

7

8

9

class Solution:
    def hasAllCodes(self, s: str, k: int) -> bool:
        n = len(s)
        m = 1 << k
        if n - k + 1 < m:
            return False
        ss = {s[i : i + k] for i in range(n - k + 1)}
        return len(ss) == m

speed

复杂度分析

指标	值
时间	complexity is O(n) because each character is processed once in the sliding window. Space complexity is O(2^k) for storing unique binary codes, which is efficient for k <= 20. Rolling hash reduces overhead compared to storing substrings directly.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Consider using a hash set instead of nested loops for substring existence checks.
question_mark
Notice that only substrings of length k matter; extra characters outside windows are irrelevant.
question_mark
Think about how bit manipulation can represent substrings compactly.

warning

常见陷阱

外企场景

error
Forgetting to handle k > length of s, which should immediately return false.
error
Recomputing substrings instead of using a rolling window, causing TLE on large strings.
error
Incorrectly counting duplicates instead of unique substrings when verifying all codes.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Check if a string contains all ternary codes of size k with characters '0', '1', '2'.
arrow_right_alt
Return the first missing binary code of length k if not all exist in s.
arrow_right_alt
Count how many binary codes of size k are present in s instead of a boolean check.

help

常见问题

外企场景

继续练习

#187 重复的DNA序列 #1525 字符串的好分割数目 #1392 最长快乐前缀