目标
给你一个二进制字符串 s 和一个整数 k 。如果所有长度为 k 的二进制字符串都是 s 的子串，请返回 true ，否则请返回 false 。
示例 1：
输入：s = "00110110", k = 2
输出：true
解释：长度为 2 的二进制串包括 "00"，"01"，"10" 和 "11"。它们分别是 s 中下标为 0，1，3，2 开始的长度为 2 的子串。示例 2：
输入：s = "0110", k = 1
输出：true
解释：长度为 1 的二进制串包括 "0" 和 "1"，显然它们都是 s 的子串。示例 3：
输入：s = "0110", k = 2
输出：false
解释：长度为 2 的二进制串 "00" 没有出现在 s 中。说明：
- 1 <= s.length <= 5 * 10^5
- s[i] 不是 '0' 就是 '1'
- 1 <= k <= 20
思路
检查一个二进制字符串是否包含所有长度为 k 的二进制子串。
长度为 k 的二进制子串的个数有 2^k 个，将子串视为二进制数字，使用长度为 k 的滑动窗口，记录窗口内子串表示的数字，判断是否所有数字都出现过即可。将左边界移出窗口需要将左边第一位置零 num = (num & (1 << (k - 1))) ^ num。先提取左边第一位，其余位均为 0，然后与 num 异或即可。
代码
/**
* @date 2026-02-24 11:31
*/
public class HasAllCodes1461 {
public boolean hasAllCodes(String s, int k) {
if (k > 18) {
return false;
}
int n = 1 << k;
boolean[] visited = new boolean[n];
int num = 0;
char[] chars = s.toCharArray();
int l = 0;
for (int r = 0; r < chars.length; r++) {
num = (num << 1) | (chars[r] - '0');
if (r - l + 1 == k) {
visited[num] = true;
num = (num & (1 << (k - 1))) ^ num;
l++;
}
}
for (boolean b : visited) {
if (!b) {
return false;
}
}
return true;
}
}
性能
