难度: Medium
给你一个二进制字符串 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 * 105s[i] 不是'0' 就是 '1'1 <= k <= 20运行时间: 225 ms
内存: 50.9 MB
class Solution:
def hasAllCodes(self, s: str, k: int) -> bool:
"""
检查是否所有长度为 k 的二进制字符串都是 s 的子串
:param s: 二进制字符串
:param k: 子串的长度
:return: 布尔值，表示是否所有长度为 k 的二进制字符串都是 s 的子串
"""
need = 1 << k
got = set()
for i in range(k, len(s) + 1):
tmp = s[i - k:i]
if tmp not in got:
got.add(tmp)
need -= 1
# 提前返回
if need == 0:
return True
return False
题解通过使用滑动窗口的方法，逐步检查每一个长度为k的子串是否存在于集合中。使用一个集合来存储已经发现的不同的子串，并使用一个变量 'need' 来记录还需要找到多少个不同的长度为k的二进制子串。初始时，'need' 等于 2^k，表示长度为k的二进制数的总数。随着新子串的添加，每次发现一个未记录的子串，'need' 就减一。如果在遍历完整个字符串前 'need' 变为0，那么说明所有可能的子串都已找到，函数返回true。如果遍历完成后，'need' 仍大于0，则返回false。
时间复杂度: O(n)
空间复杂度: O(2^k)
class Solution:
def hasAllCodes(self, s: str, k: int) -> bool:
# 计算长度为 k 的所有可能二进制数的数量
need = 1 << k
# 使用集合存储遇到的不同子串
got = set()
# 遍历字符串s，检查每个长度为k的子串
for i in range(k, len(s) + 1):
tmp = s[i - k:i]
if tmp not in got:
got.add(tmp) # 存储新的子串
need -= 1 # 减少需要找到的子串数量
# 如果已经找到所有可能的子串，提前结束
if need == 0:
return True
# 如果循环结束仍有未找到的子串，返回 False
return False
在循环中，`i`的范围是从`k`到`len(s) + 1`。这意味着最小的`i`值为`k`，此时`tmp = s[i-k:i]`将计算为`s[0:k]`，即字符串的第一个长度为`k`的子串。最大的`i`值为`len(s)`，此时`tmp`将计算为`s[len(s)-k:len(s)]`，即字符串的最后一个长度为`k`的子串。因此，循环设计确保`tmp`始终是有效的切片，不会超出字符串`s`的边界。
是的，这种方法能有效处理重复子串的情况。在代码中，每个新发现的子串在添加到集合`got`之前，会先进行检查是否已存在于集合中。只有在子串不在集合中时，才会将其添加到集合并减少`need`的值。这确保了每个子串只被计数一次，即使在原字符串中多次出现也不会重复计数，从而准确地跟踪还需要找到多少个不同的子串。
函数通过使用一个集合来存储所有已经发现的不同的子串，并追踪一个变量`need`来确保不遗漏任何子串。`need`的初始值设置为`2^k`，这是长度为`k`的所有可能二进制数的总数。每当发现一个新的不同的子串并添加到集合中时，`need`减一。如果在遍历完整个字符串前`need`变为0，这意味着所有可能的长度为`k`的二进制子串都已被发现并记录。因此，这种方法确保了不会遗漏任何子串。