Bit Manipulation     C++     Hash Function     Hash Table     Medium     Rolling Hash     String    

Problem Statement:

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

Solution:

Sol1: HashSet of int: O(n)

 
class Solution {
public:
    bool hasAllCodes(string s, int k) {
        unordered_set<int> S;
        int curr = 0, n=s.size(), useful=(1<<(k-1))-1;
        if (n<k) return false;
        for (int i=0; i<k; i++) curr = curr*2 + (s[i]-'0');
        S.insert(curr);
        for (int i=k; i<n; i++)
        {
            curr = curr&useful;
            curr = curr << 1;
            curr = curr + (s[i]-'0');
            S.insert(curr);
        }
        return S.size()==(1<<k);
    }
};

Sol2: HashSet of string: O(nk)

 
class Solution {
public:
    bool hasAllCodes(string s, int k) {
        unordered_set<string> S;
        int n=s.size();
        for (int i=0; i<n-k+1; i++) S.insert(string(s.begin()+i,s.begin()+i+k));
        return S.size()==(1<<k);
    }
};