Formatted question description: https://leetcode.ca/all/1461.html

# 1461. Check If a String Contains All Binary Codes of Size K (Medium)

Given a binary string s and an integer k.

Return True if any binary code of length k is a substring of s. Otherwise, return False.

Example 1:

Input: s = "00110110", k = 2
Output: true
Explanation: The binary codes of length 2 are "00", "01", "10" and "11". They can be all found as substrings at indicies 0, 1, 3 and 2 respectively.


Example 2:

Input: s = "00110", k = 2
Output: true


Example 3:

Input: s = "0110", k = 1
Output: true
Explanation: The binary codes of length 1 are "0" and "1", it is clear that both exist as a substring.


Example 4:

Input: s = "0110", k = 2
Output: false
Explanation: The binary code "00" is of length 2 and doesn't exist in the array.


Example 5:

Input: s = "0000000001011100", k = 4
Output: false


Constraints:

• 1 <= s.length <= 5 * 10^5
• s consists of 0's and 1's only.
• 1 <= k <= 20

Related Topics:
String, Bit Manipulation

## Solution 1. Sliding window

We can use a sliding window to keep track of the substring of length k, and mark the corresponding binary representation n as visited. Then we check if all the numbers in range [0, 2^k) are visited.

// OJ: https://leetcode.com/problems/check-if-a-string-contains-all-binary-codes-of-size-k/

// Time: O(N + min(N, 2^K))
// Space: O(2^K)
class Solution {
public:
bool hasAllCodes(string s, int k) {
vector<bool> v(1 << k);
int n = 0, mask = (1 << k) - 1;
for (int i = 0; i < s.size(); ++i) {
n = (n << 1) & mask | (s[i] - '0');
if (i >= k - 1) v[n] = true;
}
for (int i = 0; i < (1 << k); ++i) {
if (!v[i]) return false;
}
return true;
}
};


## Solution 2. Sliding window

Same idea as Solution 1, but using unordered_set to store the visited info and we just need to check the size of the set in the end.

// OJ: https://leetcode.com/problems/check-if-a-string-contains-all-binary-codes-of-size-k/

// Time: O(N)
// Space: O(2^K)
class Solution {
public:
bool hasAllCodes(string s, int k) {
unordered_set<int> st;
int n = 0, mask = (1 << k) - 1;
for (int i = 0; i < s.size(); ++i) {
n = (n << 1) & mask | (s[i] - '0');
if (i >= k - 1) st.insert(n);
if (st.size() == (1 << k)) return true;
}
return false;
}
};


Java

class Solution {
public boolean hasAllCodes(String s, int k) {
int length = s.length();
int counts = (int) Math.pow(2, k);
if (length - k + 1 < counts)
return false;
Set<String> set = new HashSet<String>();
StringBuffer sb = new StringBuffer();
for (int i = 0; i < k; i++)
sb.append(s.charAt(i));