2026-02

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

Details

给你一个二进制字符串 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 * 105
• s[i] 不是'0' 就是 '1'
• 1 <= k <= 20

这道题要求判断字符串 s 是否包含所有长度为 k 的二进制子串。下面逐步解析代码： 核心思路 长度为 k 的二进制串总共有 2^k 个（从 000...0 到 111...1）。代码用滑动窗口 + 位运算来高效地枚举 s 中所有长度为 k 的子串，检查是否覆盖了全部 2^k 种情况。 逐行解析

1. 预处理 final int MASK = (1 << k) - 1;

• 1 << k 就是 2^k，例如 k=3 时为 8（二进制 1000）。
• 减 1 得到 0111，即低 k 位全为 1 的掩码。
• 作用：后面用来截取整数的低 k 位，丢弃高位多余的比特。 boolean[] has = new boolean[1 << k];
• 大小为 2^k 的布尔数组，has[x] 表示值为 x 的长度为 k 的二进制子串是否已经出现过。 int cnt = 0; // 已经收集到的不同子串数量 int x = 0; // 当前滑动窗口对应的整数值

2. 滑动窗口遍历 for (int i = 0; i < s.length() && cnt < (1 << k); i++) {

• 遍历字符串，同时如果已经集齐所有 2^k 种子串就提前退出（剪枝优化）。

3. 位运算更新窗口 x = (x << 1 & MASK) | (ch & 1); 这是最关键的一行，拆解如下：

步骤	操作	含义
x << 1	左移一位	为新字符腾出最低位
& MASK	与掩码	只保留低 k 位，丢掉最高位（相当于窗口左边的字符滑出）
ch & 1	字符转数字	'0' 的 ASCII 码末位是 0，'1' 的末位是 1
| (ch & 1)	或运算	把新字符放到最低位（窗口右边加入新字符）
举例：k=3，MASK=0b111，当前 x=0b101(5)，新字符 '0'：

• 0b101 << 1 = 0b1010
• & 0b111 = 0b010（最高位的 1 被丢弃）
• | 0 = 0b010(2)
• 窗口从 "101" 滑动到 "010"，完全正确。

4. 记录新子串 if (i >= k - 1 && !has[x]) { has[x] = true; cnt++; }

• i >= k - 1：确保窗口已经积累了 k 个字符（前 k-1 个位置窗口还没满）。
• !has[x]：如果这个子串没见过，标记并计数。

5. 最终判断 return cnt == (1 << k);

• 收集到的不同子串数恰好等于 2^k，说明全部覆盖。 复杂度
• 时间：O(n)，遍历一次字符串
• 空间：O(2^k)，布尔数组大小 对比朴素做法 朴素做法是对每个子串调用 substring 再转整数，每次 O(k)；而这里用位运算滑动窗口，每次只需 O(1) 就能从上一个窗口推导出下一个窗口的值，效率更高。