题目链接：1461. 检查一个字符串是否包含所有长度为 K 的二进制子串（中等）
算法原理：
解法一：暴力枚举
180ms击败41.05%
时间复杂度O((n-k)k)，其中n是s的长度
心路历程：既然涉及到二进制字符串s的子串和长度为k的二进制字符串，那么我们起码要枚举出来看看是否匹配，但转念一想，长度为k的二进制字符串的个数肯定是2的k次幂，因为长度为k的各个二进制要么选1要么选0，每个二进制位都有2种选择，一共有k个二进制位，因此组合数应为2的k次幂，那么现在我们只需要确定二进制字符串s的子串的个数是否跟这个2的k次幂相等即可
其中2的k次幂可用1<<k表示，而二进制字符串s的子串的个数可借助Set的长度确定，我们利用substring来截取子串存进Set即可
解法二：递归回溯DFS
242ms击败8.73%
时间复杂度O(k*2的k次幂)
这个是最容易想到且看懂的，枚举每一位的选择（0或1），生成所有可能的k位二进制串，完成全量校验，解法一相当于直接去掉了生成的过程，直接看生成的结果个数
回溯常用到的方法 cur.deleteCharAt(cur.length()-1)，将StringBuilder最后追加的字符删掉
典型刷题例题可参考我的Java算法-递归、搜索与回溯专题1.汉诺塔~40.矩阵中的最长递增路径👇
Java算法
解法三：滑动窗口+位运算
9ms击败94.32%
时间复杂度O(N)
在暴力枚举的字符串截取上做优化，位运算比字符串截取更高效，那么我们就要完成两件事：
①用位运算代替字符串截取操作→用一个数x记录出现的各个子串，每次更新代表一个新子串
②不重不漏遍历到s的每个长度为k的子串→定长滑动窗口，通过k个1来完成出窗口和窗口内更新操作
具体步骤：
①k个连续的1咋表示：(1<<k)-1，比如k=2，1<<2=4，4-1=3，二进制为11
②定义布尔数组mark，标记该子串代表的数字x在s中是否出现过
③计数器cnt，统计出现过的不同的k位二进制子串数量
④滑动窗口的数值更新操作：
出窗口=先整体左移1位(x<<1)+清除超出k位的高位(&MASK)
更新=把字符转成整数(c&1)+该整数进窗口|(c&1)
⑤最后判断个数是否=2的k次幂
答疑
Q1：为什么位运算比字符串截取更高效？
字符串截取s.substring(i,i+k)时间复杂度O(k)，遍历整个字符串总时间位O(nk)，而位运算更新窗口值为O(1)，总时间O(n)，k越大，性能差距越明显
Java代码：
class Solution {
//解法一：暴力枚举
public boolean hasAllCodes(String s, int k) {
Set<String> hash=new HashSet<>();
for(int i=k;i<=s.length();i++)
hash.add(s.substring(i-k,i));
return hash.size()==(1<<k);
}
}
class Solution {
//解法二：递归回溯DFS
public boolean hasAllCodes(String s, int k) {
int n=s.length();
int sum=1<<k;
//剪枝：s最多能提供n+1-k个不同子串，数量不足直接返回
if(n+1-k<sum) return false;
//预处理：把s中所有长度为k的子串存入Set
Set<String> hash=new HashSet<>();
for(int i=k;i<=s.length();i++)
hash.add(s.substring(i-k,i));
//递归回溯生成所有k位二进制串
return check(k,new StringBuilder(),hash);
}
private boolean check(int k,StringBuilder cur,Set<String> hash){
//长度=k时检查是否存在
if(cur.length()==k) return hash.contains(cur.toString());
//选择1：当前位填0
cur.append('0');
boolean zero=check(k,cur,hash);
//回溯，恢复现场
cur.deleteCharAt(cur.length()-1);
//不满足直接返回
if(!zero) return false;
//选择2：当前位填1
cur.append('1');
boolean one=check(k,cur,hash);
//回溯，恢复现场
cur.deleteCharAt(cur.length()-1);
//不满足直接返回
if(!one) return false;
//两个选择都满足，返回true
return true;
}
}
class Solution {
//解法三：滑动窗口+位运算
public boolean hasAllCodes(String s, int k) {
//计算MASK：二进制为k个连续的1，作用：保留数组低k位，清除高位
final int MASK=(1<<k)-1;
//长度为2的k次幂，标记是否在s中出现过
boolean[] mark=new boolean[1<<k];
//统计出现过的不同k位二进制子串数量
int cnt=0;
//滑动窗口的当前值，用于存储滑动窗口内的二进制
int x=0;
for(int i=0;i<s.length()&&cnt<(1<<k);i++){
//拿到当前遍历的字符0或1
char c=s.charAt(i);
//O(1)完成更新
//①x<<1：x整体左移1位，给新字符腾出最低位位置
//②&MASK：出窗口操作，保留低k位，清除超出k位的高位
//③|(ch&1)：把字符转成整数放到最低位，完成滑动
x=(x<<1&MASK)|(c&1);
//只要窗口长度凑够k位，才需要判断
//0~k-1恰好k位
if(i>=k-1&&!mark[x]){
//标记出现过
mark[x]=true;
cnt++;
}
}
return cnt==(1<<k);
}
}
