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

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

题目描述

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

示例
输入：s = “00110110”, k = 2
输出：true
解释：长度为 2 的二进制串有 “00”、“01”、“10”、“11”，它们都在 s 中出现过。

解法一：哈希集合存储子串

思路

长度为 k 的二进制子串一共有 2^k 种可能。我们只需要将字符串 s 中所有长度为 k 的子串存入一个哈希集合，最后判断集合大小是否等于 2^k 即可。

剪枝优化

如果字符串的长度连理论上的最小长度都不够，那么肯定无法包含所有子串。包含所有 2^k 个二进制串的最短字符串长度是 (1 << k) + k - 1（即 de Bruijn 序列的长度）。因此可以先检查长度，快速返回 false。

代码实现

classSolution{public:boolhasAllCodes(string s,int k){// 长度预判断if(s.size()<(1<< k)+ k -1)returnfalse; unordered_set<string> strs;for(int i =0; i + k <= s.size();++i){// 截取长度为 k 的子串并插入集合 strs.insert(s.substr(i, k));}return strs.size()==(1<< k);}};

复杂度分析

• 时间复杂度：O(n·k)，其中 n 是字符串长度。需要遍历 O(n) 个子串，每次截取子串和计算哈希需要 O(k) 时间。
• 空间复杂度：O(2^k·k)，哈希集合中最多存储 2^k 个长度为 k 的字符串。

解法二：滑动窗口 + 位运算

思路

将长度为 k 的二进制子串视为一个二进制整数，取值范围为 [0, 2^k - 1]。我们可以通过滑动窗口在 O(1) 时间内计算出每个子串对应的整数值，并存入哈希集合，最后判断集合大小是否为 2^k。

滑动窗口更新公式

假设当前窗口对应的整数值为 num（窗口从下标 i 开始）。当窗口向右滑动一位时，新的窗口值为：

new_num = (old_num - (leftmost << (k-1))) * 2 + rightmost 

其中：

• leftmost 为移出窗口的最左边字符（转换为 0 或 1）
• rightmost 为新移入窗口的最右边字符

具体推导：

• 旧窗口值 num 可以表示为：leftmost * 2^(k-1) + middle，其中 middle 是后 k-1 位的数值。
• 去掉最高位后的 middle = num - (leftmost << (k-1))。
• 将 middle 左移一位（乘以 2）得到 middle * 2，相当于后 k-1 位整体左移，低位补 0。
• 加上新移入的 rightmost，得到新窗口值。

代码实现

classSolution{public:boolhasAllCodes(string s,int k){// 长度预判断if(s.size()<(1<< k)+ k -1)returnfalse;// 将前 k 个字符转换为整数int num =stoi(s.substr(0, k),nullptr,2); unordered_set<int> exists ={num};for(int i =1; i + k <= s.size();++i){// 滑动窗口更新数值 num =(num -((s[i -1]-'0')<<(k -1)))*2+(s[i + k -1]-'0'); exists.insert(num);}return exists.size()==(1<< k);}};

复杂度分析

• 时间复杂度：O(n)。每次窗口滑动只进行常数次位运算和集合插入，总时间复杂度为 O(n)。
• 空间复杂度：O(2^k)。使用整数集合存储所有可能的数值，每个整数占 4 字节，比存储字符串更节省空间。

两种解法对比

总结：解法二利用位运算将子串映射为整数，避免了字符串操作，是更优的实现。但两种方法的核心思想相同：统计所有长度为 k 的不同子串，并与总数 2^k 比较。

扩展思考

• 当 k 较大时（如 k > 20），2^k 可能超过内存限制，但题目通常保证 k ≤ 20，所以可行。
• 解法一中 s.substr(i, k) 本身返回临时对象，会自动触发移动语义，无需显式使用 move。