算法刷题系列（六十四）：二进制子串覆盖——滚动位掩码与可行性判断

算法刷题系列（六十四）：二进制子串覆盖——滚动位掩码与可行性判断

目录里的旧题问：长度为 k 的所有二进制字符串，是否都在给定字符串 s 中出现过？直接截取子串放入集合可以解决，但会反复创建短字符串。本篇使用位掩码把每个窗口编码成整数，并先用长度上界排除不可能的输入。

一、先判断输入长度够不够

长度为 k 的二进制串有 2^k 种。字符串长度为 n 时，长度为 k 的窗口最多有：

n - k + 1

如果窗口数小于 2^k，必然不可能覆盖所有编码，可以立即返回 false。这个必要条件既节省时间，也提醒我们结果状态可能需要 O(2^k) 空间。

二、滚动窗口如何编码？

把当前窗口看成一个 k 位整数。读入新位 bit 时：

mask = ((mask << 1) | bit) & ((1 << k) - 1)

左移空出最低位放新字符，再用掩码只保留最后 k 位。扫描到至少 k 个字符后，每个掩码对应一个长度为 k 的子串。

若不同掩码数量达到 2^k，所有编码都已出现。

三、Java 实现

import java.util.HashSet;
import java.util.Set;

public class BinarySubstringCoverage {
    public static boolean containsAllCodes(String text, int k) {
        if (text == null || k <= 0 || k >= 31) {
            throw new IllegalArgumentException("require text and 1 <= k < 31");
        }
        for (int i = 0; i < text.length(); i++) {
            char bit = text.charAt(i);
            if (bit != '0' && bit != '1') {
                throw new IllegalArgumentException("text must be binary");
            }
        }

        long required = 1L << k;
        if ((long) text.length() - k + 1 < required) {
            return false;
        }

        int mask = (1 << k) - 1;
        int value = 0;
        Set<Integer> seen = new HashSet<>();
        for (int i = 0; i < text.length(); i++) {
            value = ((value << 1) | (text.charAt(i) - '0')) & mask;
            if (i >= k - 1) {
                seen.add(value);
                if (seen.size() == required) {
                    return true;
                }
            }
        }
        return false;
    }
}

k < 31 确保 Java 的有符号 int 掩码表达式安全，但并不意味着如此大的 k 值适合创建集合。所需集合规模为 2^k，实际使用仍受内存限制。

四、Python 实现

def contains_all_codes(text: str, k: int) -> bool:
    if text is None or k <= 0:
        raise ValueError("require text and k > 0")
    if any(bit not in "01" for bit in text):
        raise ValueError("text must be binary")

    required = 1 << k
    if len(text) - k + 1 < required:
        return False

    mask = required - 1
    value = 0
    seen: set[int] = set()
    for index, bit in enumerate(text):
        value = ((value << 1) | int(bit)) & mask
        if index >= k - 1:
            seen.add(value)
            if len(seen) == required:
                return True
    return False

assert contains_all_codes("00110110", 2)
assert not contains_all_codes("0110", 2)
assert contains_all_codes("0", 1) is False
assert contains_all_codes("01", 1)

五、复杂度与值域取舍

设输入长度为 n：

• 时间：平均 O(n) 哈希集合操作；
• 空间：最坏 O(2^k) 个不同编码。

若 k 小且 2^k 可接受，可使用布尔数组作为 seen，并用计数器记录首次出现的编码数，减少哈希开销。若 k 很大，指数级状态空间不可避免，长度上界检查通常会尽早拒绝不可能输入。

六、常见错误

1. 判断集合大小等于 2^k 之前没有检查可行性：大 k 时可能尝试不合理内存分配。
2. 忘记只保留最后 k 位：掩码缺失时整数会持续增长，不能表示当前窗口。
3. 在窗口长度不足时也计入结果：只有读到第 k 位后才形成完整窗口。
4. 把字符字面值直接当作整数位：'0'、'1' 需要转换成数值 0、1。
5. 忽略语言整数位宽：Java 移位受 32/64 位限制，Python 大整数虽不溢出但集合规模仍指数增长。

与系列其他篇章的连接

本题结合了位运算、二进制枚举和固定窗口。它展示了“用位掩码编码窗口状态”，与状压 DP 相似，但状态数在此直接对应所有长度为 k 的字符串。

小结

滚动位掩码把长度固定的二进制窗口压缩成整数。先用窗口数量与可能编码数比较进行可行性判断，再统计出现过的编码；算法的空间上限由 2^k 决定。