## DEV Community is a community of 750,871 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

Shivam Sharma

Posted on • Updated on

# Leetcode 1461. Check If a String Contains All Binary Codes of Size K [Multiple Approaches]

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

## 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 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)`, where `N` is the size of the string and `k` 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 k-1 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 k-1 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)`, where `N` is the size of the string and `k` is the length of binary code.
• Space Complexity: `O(2^k)`

## Implementation

C++ Code:

Cover Photo by Alexander Sinn on Unsplash