先交代一下背景。LeetCode 1461 这道题题目描述很简单给一个只含0和1的字符串s再给一个整数k问这个字符串是不是包含了所有长度为k的二进制子串。我第一次刷到这道题的时候第一反应是这有什么好检查的把子串都列出来不就行了结果真动手写才发现这里面有几个坑而且解法从暴力到优化能拉开好几个档次。这篇就把这道题的完整思路、代码实现、位运算优化以及它背后藏着的 De Bruijn 序列知识一次讲透适合正在刷字符串类题目的朋友也适合想搞明白为什么用哈希集合这类问题的读者。1. 读懂题目长度为 K 的二进制子串到底有几种先别急着写代码把题目里的数量关系理清楚这道题其实就成功了一半。长度为k的二进制子串每一位都只能是0或1所以一共有2^k种不同的组合。比如k 2时所有可能的子串是00、01、10、11共 4 种k 3时就是000、001、010、011、100、101、110、111共 8 种。题目要判断的是给定的字符串s里这2^k种组合是不是全都出现过缺任何一种都不行。这里有个很重要的前提——字符串s的长度是n那么长度为k的子串一共有多少个答案是n - k 1个。例如s 10110长度为 5当k 2时子串依次是10、01、11、10确实只有5 - 2 1 4个。把这两件事放到一起就得出一个很多人会忽略的必要条件如果n - k 1 2^k也就是字符串里的子串总数都凑不够2^k种那答案直接就是false根本不用做任何进一步判断。举个例子s 00110k 2。n 5n - k 1 4而2^k 4数量上刚好够。再看s 00101k 3n 5子串总数是 3但2^3 83 个位置无论如何也不可能覆盖 8 种组合所以必然返回false。这个判断看起来简单但在实战中非常有用。很多人的第一版代码上来就是滑动窗口 哈希集合等到最后判断set.size()是否等于2^k时才反应过来数量不够。提前用这个必要条件做剪枝既省时间又省内存。不过也要注意这个条件是必要但不充分的。子串数量够不代表每种组合都出现。比如s 00000k 2子串总数是 4恰好等于2^2但 4 个子串全是00显然不满足要求。所以数量检查只能用来提前排除不能用来直接判定通过。2. 暴力枚举为什么不划算先算清复杂度再动手很多人包括我一开始想的暴力解法是这样的把所有2^k种二进制串全部构造出来然后逐个去s里用indexOf或find查找有一个找不到就返回false。这个思路在k很小的时候没问题但一旦把数据范围放进去就完全不行了。LeetCode 上这题的约束是s.length最大到5 * 10^5k最大到20。为什么k最大只给到 20因为2^20 1,048,576刚好是一百万出头这个数字作为哈希集合或者布尔数组的大小还能接受。如果你把k提到 252^25已经超过 3300 万内存明显吃不消所以题目设计者把k限制在 20 是有数学道理的。回到暴力解法枚举2^k种子串每个子串长度又是k在s里做一次查找最坏是O(n * k)所以整体复杂度大约O(2^k * n * k)。当k 20、n 5 * 10^5时这个数字大约是10^6 * 5 * 10^5 * 20也就是10^13量级跑完基本等于等到天荒地老。还有人会想到第二种暴力把s里的所有长度为k的子串截出来放到列表里然后对列表去重最后看去重后的数量是不是2^k。这种方式其实已经接近正确解法了但有一个致命问题——如果用的是List.contains()或者类似方法来判断去重那每一次判断都要遍历整个列表复杂度退化到O(n * k * 2^k)同样不可接受。这两种暴力方案失败的核心原因都是没有找到一个近似 O(1) 的判重手段。要么查找太慢要么去重太慢。解法其实很朴素用哈希集合把去重这件事从O(数量)降到O(1)平均时间复杂度。这也是为什么下一节的滑动窗口 哈希集合能成为标准解法。3. 滑动窗口加哈希集合标准解法其实是在数种类正确解法很好理解维护一个长度为k的滑动窗口每滑动一次就得到一个长度为k的子串把它丢进一个HashSet最后看set.size()是不是等于2^k。class Solution { public boolean hasAllCodes(String s, int k) { int n s.length(); if (n - k 1 (1 k)) { return false; } SetString set new HashSet(); for (int i 0; i k n; i) { set.add(s.substring(i, i k)); if (set.size() (1 k)) { return true; } } return set.size() (1 k); } }这里有几个细节值得展开讲。第一个细节为什么不把所有子串都加完再判断因为题目只问是否包含全部组合不要求你统计到底有几种。只要set.size()已经达到2^k那说明所有组合都出现了后续的子串再多也没有意义可以直接返回true。这个提前返回在运气好的情况下能省不少时间特别是那些测试用例很快就能集齐全部组合的场景。第二个细节为什么用Set而不直接数因为同一个子串可能重复出现很多次比如s 000000里00出现了 5 次但只能算一种。HashSet天然去重size()就是不同子串的种类数。你要换成数组或者列表去重逻辑就麻烦了。第三个细节子串截取的时间复杂度。s.substring(i, i k)在 Java 里需要拷贝k个字符所以这一步是O(k)的。整体复杂度是O(n * k)在n 5 * 10^5、k 20时大约是一千万次字符操作对现代 CPU 来说完全没压力。空间复杂度是O(2^k)用来存这么多不同的子串。Python 版本的写法类似class Solution: def hasAllCodes(self, s: str, k: int) - bool: n len(s) if n - k 1 (1 k): return False seen set() for i in range(n - k 1): seen.add(s[i:i k]) if len(seen) (1 k): return True return len(seen) (1 k)两种语言的核心思路完全一样都是滑动窗口枚举所有子串 哈希集合去重计数。这道题做到这一步其实已经能通过了时间复杂度也能接受。但从刷题和面试的角度来说如果能在标准解基础之上再做一层位运算优化会显得你对字符串底层的理解更到位这也是下一节要讲的内容。4. 位运算优化把子串当成一个整数来滚动前面用substring截取子串本质上是把每个长度为k的窗口当成一个字符串来处理。但如果换个角度想——长度为k的二进制子串本质上就是一个k位的二进制数范围从0到2^k - 1。既然这样我们完全可以用一个整数val来表示当前窗口的内容每次窗口滑动时只需要把这个整数做一次左移、加上新位、与掩码操作就能得到新窗口对应的数值。具体来说假设当前窗口对应的二进制数是val现在窗口向右滑动一格新进来的字符是c0或1那么新窗口对应的数就是val ((val 1) | (c - 0)) ((1 k) - 1)拆开来看val 1相当于把原来的k位二进制数整体左移一位最右边的空位补0| (c - 0)把新字符的值填入最低位 ((1 k) - 1)把结果限制在k位以内把超出k位的最高位丢弃。因为(1 k) - 1的二进制表示就是k个1任何数和它做与运算都只会保留低k位。这个思路本质上就是滚动哈希Rabin-Karp algorithm的最简形态也叫滑动窗口位运算。class Solution { public boolean hasAllCodes(String s, int k) { int n s.length(); if (n - k 1 (1 k)) { return false; } int mask (1 k) - 1; boolean[] seen new boolean[1 k]; int val 0; for (int i 0; i n; i) { val ((val 1) | (s.charAt(i) - 0)) mask; if (i k - 1) { if (!seen[val]) { seen[val] true; int count 0; for (boolean v : seen) { if (v) count; } if (count (1 k)) { return true; } } } } for (boolean v : seen) { if (!v) return false; } return true; } }这段代码里我故意用了遍历数组来统计seen的数量实际写的时候可以在外部维护一个count变量每次seen[val]从false变成true时count这样就不用每次都遍历整个数组了。优化后的版本class Solution { public boolean hasAllCodes(String s, int k) { int n s.length(); if (n - k 1 (1 k)) { return false; } int mask (1 k) - 1; boolean[] seen new boolean[1 k]; int val 0; int count 0; for (int i 0; i n; i) { val ((val 1) | (s.charAt(i) - 0)) mask; if (i k - 1) { if (!seen[val]) { seen[val] true; count; } if (count (1 k)) { return true; } } } return count (1 k); } }这里有一个很容易踩的坑什么时候才开始记录第一个val必须是i k - 1也就是窗口已经完整覆盖了k个字符之后。如果i k - 1比如k 3而你只读了 2 个字符val实际上是一个长度不足 3 的二进制数把它记录进去会把结果搞乱。这跟之前用substring时i k n的限制是对应的。另一个更隐蔽的坑是忘记与掩码做与运算。val经过多次左移之后高位会积累旧的字符信息。比如k 3你处理完前面 4 个字符后val如果不做掩码处理保存的是 4 位甚至更多的二进制数这就不是当前窗口的内容了。只有每次都与mask做与运算才能保证val始终是一个k位二进制数。我实测过把这个 mask去掉之后代码在部分用例上会得到完全错误的结果而且这种 bug 很难一眼看出来因为大部分用例可能刚好不受影响。boolean[]对比HashSet的优势也很明显数组索引就是val本身不需要额外哈希计算也不存在哈希冲突空间上2^20个布尔值大约 1MB完全可接受。实际跑下来位运算版本比字符串截取版本快了将近一个数量级在 LeetCode 上的耗时差距非常明显。5. 这道题背后的数学知识De Bruijn 序列与最短超串讲完优化再往深挖一层。LeetCode 1461 这个题目其实和组合数学里的一个经典概念——De Bruijn 序列关系非常紧密。De Bruijn 序列的定义是对于一个字符集大小为k、长度为n的循环序列它包含了所有长度为n的字符组合并且每种组合恰好出现一次在循环意义上。放到这道题的语境里字符集是{0, 1}大小是 2要找的是包含所有长度为k的二进制子串的最短字符串。这个最短字符串的长度是多少答案是2^k k - 1。为什么是这个数因为长度为k的子串一共有2^k种如果想让字符串最短那这2^k个子串在字符串中应该是无缝衔接的——后一个子串的前k - 1位就是前一个子串的后k - 1位。每增加一个新子串只需要增加 1 个字符。所以最短长度 第一个子串的k个字符 后面2^k - 1个子串各贡献 1 个字符 k 2^k - 1。举个例子k 3时最短字符串长度为8 3 - 1 10。可以构造出00010111或00011101这两个字符串都包含了000、001、010、101、011、111、110、100全部 8 种长度为 3 的二进制子串。De Bruijn 序列的构造方法有很多一组常用的构造方式是使用 Lyndon word 拼接或者用贪心的 Eulerian path / Hierholzer 算法。下面我给出一个最容易理解的构造代码思路是把所有长度为k - 1的二进制串当成图中的节点每个节点有两条出边一条标记为0到达左移后最低位补0的节点另一条标记为1到达左移后最低位补1的节点。然后在这个图上找一条经过所有边恰好一次的路径欧拉路径路径上依次经过的边标签连起来就是 De Bruijn 序列。def de_bruijn(k: int): # k 是子串长度 seen set() seq [] # 起点是所有 k-1 位都是 0 的节点 start 0 * (k - 1) def dfs(node): for bit in 01: edge node bit if edge not in seen: seen.add(edge) dfs(edge[1:]) seq.append(bit) dfs(start) # 需要补上 k-1 个前导 0因为欧拉路径只覆盖了每条边一次 return .join(seq) # 验证一下 s de_bruijn(3) print(s, len(s)) # 输出类似于 10111000长度为 11等等仔细看这个构造方法它产生的是长度为2^k k - 1的序列里面包含了所有长度为k的二进制子串而且每一种恰好出现一次。这个长度比循环最短多出了k - 1个字符目的是让序列在非循环意义下也满足条件。这里有个细节为什么上面de_bruijn(3)的长度是 11因为我们需要的是一个线性字符串而不是循环序列。非循环的 De Bruijn 序列长度就是2^k k - 1不是2^k。回到题目本身如果s的长度恰好等于2^k k - 1而且答案是真那s本身就大概率构成一个 De Bruijn 序列或者说它包含了所有k位二进制子串。但题目允许s更长所以没必要真的去构造 De Bruijn 序列然后比较哈希集合法直接解决问题但理解 De Bruijn 序列能帮你更深刻地理解这道题的结构。从这道题还能得到一个通用结论判断短模式串集合是否完全出现在长文本中最优做法就是窗口滑动 集合记录 数量判定这三板斧在字符串处理中反复出现。6. 实战复盘同类题、常见错误和我的做题习惯最后复盘一下这道题涉及的技巧在 LeetCode 里不是孤立的。最直接的同类题是187. Repeated DNA Sequences那道题要求在 DNA 序列字符集A/C/G/T里找出所有出现超过一次的长度为 10 的子串。解题思路几乎一模一样——滑动窗口 哈希表计数只是字符集不是二进制的0/1而是 4 种字符所以可以用2 bit编码一个字符00表示 A01表示 C10表示 G11表示 T窗口长度 10 就是 20 个 bit刚好放在一个 int 里。这种编码技巧和本题的位运算优化完全一致。再往上走这道题又是Rabin-Karp 字符串匹配和滚动哈希思想的极简演示。Rabin-Karp 的核心就是把字符串当成一个多进制的数用滑动窗口维护这个数的值和本题val ((val 1) | bit) mask的处理方式如出一辙只不过这里进制是 2掩码是2^k - 1而 Rabin-Karp 通常用一个大质数取模。实战中最常见的四个错误我挨个说一遍。第一个不做数量预判。上来就开数组或哈希集等到边界判断时才发现s根本没那么长子串白白浪费时间和内存。第二个位运算没掩码。前面详细说了忘记 mask会让val混入窗口之外的高位垃圾数据得到完全错误的判定结果。第三个用List.contains去重。这样的代码在小数据集上看起来没问题一上大数据就超时原因就是去重从 O(1) 退化成了 O(n)。第四个混淆所有子串互不相同和包含所有组合。s 00000k 2它能列出的子串只有00一种当然谈不上互不相同反过来如果s 0101k 2子串是01、10、01集合大小为 2而2^2 4缺少00和11答案是false。判断标准永远是set.size() 2^k不是有没有重复子串。我个人的做题习惯是遇到这类字符串是否包含所有短模式的问题先花三十秒算出两件事——全集规模2^k和文本子串总量n - k 1。如果全集规模超过能接受的内存范围立刻思考有没有状态压缩或者数学构造的思路如果子串总量连全集都凑不够直接写剪枝返回。然后优先用位运算滚动维护窗口值而不是字符串截取这样既快又能减少内存分配。这套思考流程不一定每次都能一步写出最优解但能保证不走弯路。就这道题来说从暴力到哈希集合法到位运算优化每一步都是顺理成章的事。刷题不只是为了 AC 一个用例把这个递进过程吃透以后碰到任何窗口子串计数类问题你的第一反应都会比原来快很多。