1461. Check If a String Contains All Binary Codes of Size K¶
题目信息¶
- 题号:
1461
- 难度:
Medium
- 主题:
字符串、滑动窗口、哈希集合、位运算
- 原题:
- 重点:
检查全部
2^k个长度为k的二进制字符串是否都作为连续子串出现
题目重述¶
给定二进制字符串 s 和正整数 k。长度为 k 的二进制编码共有 2^k 种。
若每一种编码都至少一次作为 s 的连续子串出现,返回 true;否则返回 false。不同编码的出现区间可以重叠。
1 <= s.length <= 5 * 10^5,1 <= k <= 20。
自建示例¶
重叠窗口可以覆盖全部编码:
输入:s = "00110", k = 2
输出:true
解释:长度为二的子串依次包含 00、01、11、10,覆盖全部四种编码。
字符串长度小于 k 时必然失败:
输入:s = "0", k = 2
输出:false
解释:不存在长度为二的连续子串。