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

题目描述#

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

示例 1：

1
输入：s = "00110110", k = 2
2
输出：true

示例 2：

1
输入：s = "0110", k = 1
2
输出：true

示例 3：

1
输入：s = "0110", k = 2
2
输出：false

核心思想#

一个长度为 k 的二进制子串，本质上就是一个 k 位的二进制数，其取值范围是 0 到 2^k - 1，一共 2^k 种可能。

所以题目等价于：s 中所有长度为 k 的子串组成的整数集合，是否恰好覆盖了 [0, 2^k) 的全部 2^k 个值。

基于这个思路，我们只需用定长滑动窗口扫一遍 s，把每个长度为 k 的窗口对应的整数记录下来，最后看是不是 2^k 个都出现了。由于 k ≤ 20，2^k 最多约 10^6，用一个布尔数组即可。

位运算滚动窗口：O(1) 维护窗口整数#

暴力把每个窗口切片再转 int 是 O(k) 的。我们可以用滚动窗口 + 位运算把它优化成 O(1)：

维护一个整数 val，表示当前窗口内 k 位二进制串对应的数值。窗口每向右移动一位：

入：val = (val << 1) | bit，即把旧窗口值左移一位，空出的最低位填充新字符 bit。
截断：val = val & mask，其中 mask = 2^k - 1，只保留低 k 位（k 个 1），把多余的进位清掉，等价于”左端点离开窗口”。

这两个操作合在一起正好是 val = ((val << 1) | bit) & mask，一步完成”入”和”出”。

当索引 i >= k - 1 时，说明窗口已经形成（长度恰好为 k），此时把 val 标记为已出现。

算法步骤#

令 need = 2^k，mask = need - 1，初始化 seen = [False] * need，val = 0。
从左到右遍历 s：
- 更新 val = ((val << 1) | (ord(ch) - ord('0'))) & mask。
- 若 i >= k-1（窗口长度已凑够 k），将 seen[val] = True。
返回 all(seen)，即所有 2^k 种取值是否都出现过。

逐步举例#

以 s = "0110", k = 2 为例：need = 4, mask = 3。

i	ch	val = ((val<<1)\|bit) & mask	i>=1 ?	seen 标记
0	’0’	((0<<1)\|0)=0 & 3 = 0	否跳过	—
1	’1’	((0<<1)\|1)=1 & 3 = 1	是	seen[1]=1
2	’1’	((1<<1)\|1)=3 & 3 = 3	是	seen[3]=1
3	’0’	((3<<1)\|0)=6 & 3 = 2	是	seen[2]=1

最终 seen[0..3] = [F,T,T,T]，seen[0]=False，即长度为 2 的二进制串 "00" 没有出现。返回 false。✅

代码实现#

1
class Solution:
2
    def hasAllCodes(self, s: str, k: int) -> bool:
3
        need = 1 << k
4
        seen = [False] * need
5
        mask = need - 1
6
        val = 0
7
        for i, ch in enumerate(s):
8
            val = ((val << 1) | (ord(ch) - 48)) & mask
9
            if i >= k - 1:
10
                seen[val] = True
11
        return all(seen)

1
import sys
2
sys.path.insert(0, "/workspace/projects/source/coding/sliding-window-two-pointers/01-fixed-sliding-window/1461-all-binary-codes")
3
from solution import Solution
4
import unittest
5

6
class TestHasAllCodes(unittest.TestCase):
7
    def setUp(self):
8
        self.solution = Solution()
9

10
    def test_example1(self):
11
        self.assertTrue(self.solution.hasAllCodes("00110110", 2))
12

13
    def test_example2(self):
14
        self.assertTrue(self.solution.hasAllCodes("0110", 1))
15

16
    def test_example3(self):
17
        self.assertFalse(self.solution.hasAllCodes("0110", 2))
18

19
    def test_long_string(self):
20
        s = "0" * 10000 + "1" * 10000
21
        self.assertFalse(self.solution.hasAllCodes(s, 10))
22

23
    def test_small_k(self):
24
        self.assertTrue(self.solution.hasAllCodes("01", 1))
25

26
    def test_not_enough(self):
27
        self.assertFalse(self.solution.hasAllCodes("000", 2))
28

29
if __name__ == "__main__":
30
    unittest.main()

复杂度分析#

时间复杂度：O(n)，其中 n 是 s 的长度，每次更新窗口都是 O(1)。
空间复杂度：O(2^k)，布尔数组 seen 的大小，k ≤ 20 时最多约 10^6。