Leetcode 1461. Check If a String Contains All Binary Codes of Size K [Multiple Approaches]
Tags: algorithms, programming, cpp, tutorial
Published: 2021-03-12 18:13:46

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](#problem-statement)
* [Explanation](#explanation)
* [Solution](#solution)
	* [Approach 1 (Using Set/Bitset)](#app-1)
	* [Approach 2 (Using Rolling Hash)](#app-2)
* [Implementation](#implementation)

---

## Problem Statement <a name="problem-statement"></a>

**Question:** [https://leetcode.com/problems/check-if-a-string-contains-all-binary-codes-of-size-k/](https://leetcode.com/problems/check-if-a-string-contains-all-binary-codes-of-size-k/)

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 <a name="explanation"></a>
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 <a name="solution"></a>
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: <a name="app-1"></a>

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](http://www.cplusplus.com/reference/unordered_set/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`.

```cpp
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.

```cpp
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](http://www.cplusplus.com/reference/bitset/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`.

```cpp
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](https://en.wikipedia.org/wiki/Rolling_hash))<a name="app-2"></a>
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:
```c#
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](https://leetcode.com/problems/check-if-a-string-contains-all-binary-codes-of-size-k/discuss/1106013/Short-Fast-and-Easy-w-explanation-or-Multiple-Approaches-or-beats-100) given by [Abhishek](https://leetcode.com/archit91/).

So as per above approach the code is below:
```cpp
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 <a name="implementation"></a>

**C++ Code:**

{% replit @shivams136/Leetcode-1461-Check-If-a-String-Contains-All-Binary-Cod %}

Cover Photo by <a href="https://unsplash.com/@swimstaralex?utm_source=unsplash&utm_medium=referral&utm_content=creditCopyText">Alexander Sinn</a> on <a href="/s/photos/binary?utm_source=unsplash&utm_medium=referral&utm_content=creditCopyText">Unsplash</a>