This is a very interesting question that can check your thinking ability and knowledge about bitwise operators. I have mentioned 2 different approaches and 3 code samples. You must solve this.
Difficulty: Medium
Jump To:
Problem Statement
Question: https://leetcode.com/problems/checkifastringcontainsallbinarycodesofsizek/
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 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
Explanation
The problem is simple, we just need to check if every binary code of length k
is a substring of s
. For example, if k=2
then binary code representation of length 2 are 00
, 01
, 10
, and 11
. So the string s
must include all these values like the string 00110
has i.e. 00 110, 0 01 10, 00 11 0, and 001 10 . So if the string has every binary code of length k
as a substring in s
then return true
else false
.
Solution
The naive approach can be to first find all the combinations of the binary string of length k
and then check if each of these combinations is a substring to the string. But this is a very heavy approach as time complexity can be O(N*2^k)
. So let's discuss the more efficient approaches as below:
Approach 1:
We can say that it's the reverse approach, instead of checking for each combination being a substring of s
or not, we'll count all the distinct substrings of length k
in s
is equal to 2^k
or not. Because for any binary string of length k
we can get maximum 2^k
combinations as we saw in the above example that for k=2
we have 2^2 = 4
combinations.
To count distinct substrings inside s
of length k
we will be using a set or unordered_set, as we know that a set can contain only distinct values so we'll add each substring of length k
in this set. In the end, if the total number of items in this set is equal to 2^k
then we return true
else false
.
class Solution {
public:
bool hasAllCodes(string s, int k) {
unordered_set<string> substr_set;
int len = s.size();
int no_of_comb = (1<<k);
for(int i = 0; i+k <= len && substr_set.size() != no_of_comb; i++){
substr_set.insert(s.substr(i,k));
}
return substr_set.size() == no_of_comb;
}
};
The above solution can be improved as every binary string represents a number as well so instead of inserting a string in the set we'll be inserting its decimal value in the set. so less space will be used.
class Solution {
public:
bool hasAllCodes(string s, int k) {
unordered_set<int> substr_set;
int len = s.size();
int no_of_comb = (1 << k);
for(int i = 0; i+k <= len && substr_set.size() != no_of_comb; i++){
substr_set.insert(stoi(s.substr(i,k),nullptr,2));
}
return substr_set.size() == no_of_comb;
}
};
The above solution can be further improved using bitset instead of a set, as every binary string represents a number let's say n
so instead of inserting in the set we'll be setting n
th bit in the bitset and at the end, we'll be counting set bits in the bitset and check if it is equal to 2^k
then return true
else false
.
class Solution {
public:
bool hasAllCodes(string s, int k) {
bitset<(1<<20)> bset;
int len = s.size();
for(int i = 0; i+k <= len; i++){
bset[stoi(s.substr(i,k),nullptr,2)] = 1;
}
return bset.count() == (1<<k);
}
};

Time Complexity:
O(N*k)
, whereN
is the size of the string andk
is the length of binary code. 
Space Complexity:
O(N*k)
Approach 2 (Using Rolling Hash)
We don't even need to calculate the full value let's say hash
for each of the substring of length k
using stoi()
as we were doing so in the last approach. We can just calculate hash
for the first substring of length k
and thereafter, we can apply rolling hash technique.
This approach is nothing but removing the last character of the previous substring and adding the next character from s
and calculating the hash from this instead of recalculating the whole hash.
Let's understand this with the below example:
hash = hash << 1 : one shift to left
hash &= allOnes : removes kth bit, ensures our hash always less than 2^k
hash = s[i]  '0' : calculates hash with new character after removing first character of previous substring
Eg. Suppose string is 110101 and k = 3. We start with hash = 0. Here size = 2^k = 8 and allOnes = 7 (111).
1. hash = 000 << 1 = 000  hash &= (111) = 000(0)  hash = 1 = 001 ðŸ‘‰ hash = 001 (1)
2. hash = 001 << 1 = 010  hash &= (111) = 010(2)  hash = 1 = 011 ðŸ‘‰ hash = 011 (3)
3. hash = 011 << 1 = 110  hash &= (111) = 110(6)  hash = 0 = 110 ðŸ‘‰ hash = 110 (6)
4. hash = 110 << 1 = 1100  hash &= (111) = 100(4)  hash = 1 = 101 ðŸ‘‰ hash = 101 (5)
^exceeds (2^k) ^2nd step removes kth bit^
5. hash = 101 << 1 = 1010  hash &= (111) = 010(2)  hash = 0 = 010 ðŸ‘‰ hash = 010 (2)
6. hash = 010 << 1 = 100  hash &= (111) = 100(4)  hash = 1 = 101 ðŸ‘‰ hash = 101 (5)
We can observe that using rolling hash, after first k1 steps, our hash value is always equal
to the decimal equivalent of substring of length k. This can be used as for indexing the set which
will store the distinct substrings of length k found. If number of distinct substrings is equal to size,
then the answer will be true.
I picked this great explanation from this Leetcode discuss post given by Abhishek.
So as per above approach the code is below:
class Solution {
public:
bool hasAllCodes(string s, int k) {
int n=s.size(),
size=1<<k, // This results in 2^k
count=0, // count to store distinct substrings found
hash=0, // rolling hash variable
allOnes= ~size; // this results in a 0 followed by k 1's
bitset<(1<<20)> bset; // Bitset to store found substr
for(int i=0; i<n; i++){
// Rolling hash calculation
hash = ((hash << 1) & allOnes)  (s[i]  '0');
// Skip first k1 hash and check if this string is not found yet
if(i >= k  1 && !bset[hash]){
// Set bit to mark substr found
// Increase count
bset[hash] = true, count++;
if(count == size) // If all substr are found
break;
}
}
return count == size;
}
};

Time Complexity:
O(N)
, whereN
is the size of the string andk
is the length of binary code. 
Space Complexity:
O(2^k)
Implementation
C++ Code:
Cover Photo by Alexander Sinn on Unsplash
Top comments (0)