LeetCode 1461. 检查一个字符串是否包含所有长度为 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 字节，比存储字符串更节省空间。

两种解法对比

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

扩展思考

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