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。

代码实现

class Solution {
public:
    bool hasAllCodes(string s, int k) {
        // 长度预判断
        if(s.size() < (1 << k) + k - 1) return false;
        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，得到新窗口值。

代码实现

class Solution {
public:
    bool hasAllCodes(string s, int k) {
        // 长度预判断
        if(s.size() < (1 << k) + k - 1) return false;
        // 将前 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 字节，比存储字符串更节省空间。

---

两种解法对比

方法	时间复杂度	空间复杂度	适用场景
哈希集合（子串）	O(n·k)	O(2^k·k)	代码简单，适合 k 较小的情况
滑动窗口 + 位运算	O(n)	O(2^k)	效率更高，k 较大时不易超时

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

---

扩展思考

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