1461

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 every 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 indices 0, 1, 3 and 2 respectively.

Example 2:

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 3:

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

 

Constraints:

• 1 <= s.length <= 5 * 105
• s[i] is either '0' or '1'.
• 1 <= k <= 20

Related Topics:
Hash Table, String, Bit Manipulation, Rolling Hash, Hash Function

NOTE

Bitwise AND has higher priority than bitwise OR according to https://en.cppreference.com/w/cpp/language/operator_precedence. So

cout << bitset<3>(0b110 | 1 & 0b11) << " " << bitset<3>(0b110 & 0b11 | 1) << endl;
// 111 011

For k = 20, there are at most 2^k ~= 1e6 binary codes.

We can use a sliding window of length k to scan all the binary codes that can be generated from s.

For s.length = 5e5, there are at most 5e5 - 19 codes. We can save them in a set. If the size of set becomes 2^k, we've seen all the binary codes.

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/
// Author: github.com/lzl124631x
// 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;
    }
};

Or

// OJ: https://leetcode.com/problems/check-if-a-string-contains-all-binary-codes-of-size-k/
// Author: github.com/lzl124631x
// Time: O(min(N, 2^K))
// Space: O(2^K)
class Solution {
public:
    bool hasAllCodes(string s, int k) {
        vector<bool> v(1 << k);
        int mask = (1 << k) - 1, cnt = 1 << k, n = 0;
        for (int i = 0; i < s.size() && cnt; ++i) {
            n = n << 1 & mask | (s[i] - '0');
            if (i >= k - 1) {
                if (!v[n]) --cnt;
                v[n] = true;
            }
        }
        return cnt == 0;
    }
};

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/
// Author: github.com/lzl124631x
// 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;
    }
};