题目大意：
检查一个字符串是否包含所有长度为 K 的二进制子串
给你一个二进制字符串 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 = "00110", k = 2 输出：true
示例 3：
输入：s = "0110", k = 1 输出：true 解释：长度为 1 的二进制串包括 "0" 和 "1"，显然它们都是 s 的子串。
示例 4：
输入：s = "0110", k = 2 输出：false 解释：长度为 2 的二进制串 "00" 没有出现在 s 中。
示例 5：
输入：s = "0000000001011100", k = 4 输出：false
提示：
1 <= s.length <= 5 * 10^5s中只含 0 和 1 。1 <= k <= 20
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1461
解题思路分析：
题目的问题是所有长度为k的二进制串是否都是s的子串。如果使用暴力方式遍历每一个二进制字符串，然后再去与s进行contains操作的话，大概率会超时。本题我们需要换一个角度去思考，首先所有长度为k的二进制串一定都是不重复的，因为这些二进制串分别代表了数字0到长度为k的最大二进制数（k个1）。那么我们只要判断一下s中所有长度为k并且不重复的子串个数是否等于长度为k的最大二进制数加一即可（加一的目的是包含二进制数0）。统计s中长度为k的不重复子串很简单，我们使用Set类来排重，然后循环一遍s中所有长度为k的区间，将区间内的子串加入Set即可。
实现代码：
public boolean hasAllCodes(String s, int k) {
if(k>s.length()) return false; // 如果k大于字符串s的长度，返回false
// 长度为k的子串
StringBuilder sb=new StringBuilder();
// 保存所有不重复的子串
Set<String> set=new HashSet<>();
// 为了提高效率，将字符串转为字符数组
char[] arr=s.toCharArray();
// 得到第一个长度为k的子串
for(int i=0;i<k;i++){
sb.append(arr[i]);
}
// 加入set
set.add(sb.toString());
// 循环后续所有长度为k的子串
for(int i=k;i<s.length();i++){
// 删除原子串首字符，再在尾部加上一个新字符
sb.deleteCharAt(0).append(arr[i]);
set.add(sb.toString()); // 加入set
}
// 查看set中元素数量是否等于长度为k的二进制串数量
return set.size()==(1<<k);
} 本题解法执行时间为153ms。
Runtime: 153 ms, faster than 47.34% of Java online submissions for Check If a String Contains All Binary Codes of Size K.
Memory Usage: 56.2 MB, less than 100.00% of Java online submissions for Check If a String Contains All Binary Codes of Size K.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1461-check-if-a-string-contains-all-binary-codes-of-size-k-解题思路分析/