1461. Check If a String Contains All Binary Codes of Size K

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/
// 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;
    }
};