Solution: Check If a String Contains All Binary Codes of Size K
Tags: algorithms, javascript, java, python
Published: 2021-03-12 11:00:28

*This is part of a series of Leetcode solution explanations ([index](https://dev.to/seanpgallivan/leetcode-solutions-index-57fl)). If you liked this solution or found it useful,* ***please like*** *this post and/or* ***upvote*** *[my solution post on Leetcode's forums](https://leetcode.com/problems/check-if-a-string-contains-all-binary-codes-of-size-k/discuss/1105899).*

---

#### [Leetcode Problem #1461 (*Medium*): 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/)

---

#### ***Description:***

<br />(*Jump to*: [*Solution Idea*](#idea) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

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

---

#### ***Examples:***
>
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`

---

#### ***Idea:***

<br />(*Jump to*: [*Problem Description*](#description) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

The naive solution would be to iterate through the possible binary strings and check through the input string (**S**) to see if each one exists, but this would quickly run into a **TLE**.

Instead, we'll have an easier time solving this problem from the opposite direction. We can iterate through **S** and make a note of every number that's been **seen**. This also brings up a more interesting point: with such a relatively small constraint upon the length of **S**, it limits how many possible numbers a string can produce.

If we think of a **sliding window** of **K** width moving down **S**, then it becomes obvious that there can be at most **S.length - K + 1** possible different numbers. Since the length of **S** is constrained to **5e5**, that means that the answer will automatically be **false** at **K** values of **19** and **20**, for example.

In our solution, however, we can just choose to iterate through **S** backwards, and use our index (**i**) as a way to keep track of how many iterations remain, and therefore how many chances are left to find any remaining numbers. If at any time the amount of numbers left to find (**count**) is less than than **i**, then there's no way to get to true, so we should **return false**.

On the other hand, if **count** is reduced to **0**, then we have found all the numbers and can **return true**.

In order to be as performant as possible, we can use a lightweight **typed array** for **seen**. To keep from having to repeatedly obtain and convert **substrings**, we can use **bit manipulation** to modify the previous **num** with the new character from **S** to obtain the new **num**.

---

#### ***Implementation:***

Javascript doesn't have a boolean typed array, but we can use a **Uint8Array** instead.

Python doesn't have a faster typed array and it deals with slices faster than other languages, so it actually makes sense to use a **set()** and leave the binary strings as strings.

---

#### ***Javascript Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```javascript
var hasAllCodes = function(S, K) {
    let len = S.length, count = 1 << K,
        seen = new Uint8Array(count),
        num = parseInt(S.slice(len - K + 1), 2) << 1
    for (let i = len - K; ~i; i--) {
        num = ((S.charAt(i) << K) + num) >> 1
        if (!seen[num]) seen[num] = 1, count--
        if (!count) return true
        if (i < count) return false
    }
};
```

---

#### ***Python Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```python
class Solution:
    def hasAllCodes(self, S: str, K: int) -> bool:
        count = 1 << K
        seen = set()
        for i in range(len(S) - K, -1, -1):
            num = S[i:i+K]
            if num not in seen:
                seen.add(num)
                count -= 1
            if not count: return True
            if i < count: return False
```

---

#### ***Java Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```java
class Solution {
    public boolean hasAllCodes(String S, int K) {
        int len = S.length(), count = 1 << K;
        if (K > len) return false;
        int num = K > 1 ? Integer.parseInt(S.substring(len - K + 1), 2) << 1 : 0;
        boolean[] seen = new boolean[count];
        for (int i = len - K; i >= 0; i--) {
            num = (((S.charAt(i) - '0') << K) + num) >> 1;
            if (!seen[num]) {
                seen[num] = true;
                count--;
            }
            if (count == 0) return true;
            if (i < count) return false;
        }
        return false;
    }
}
```

---

#### ***C++ Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```c++
class Solution {
public:
    bool hasAllCodes(string S, int K) {
        int len = S.size(), count = 1 << K;
        if (K > len) return false;
        int num = K > 1 ? stoi(S.substr(len - K + 1), 0, 2) << 1 : 0;
        vector<bool> seen(count, false);
        for (int i = len - K; ~i; i--) {
            num = (((S[i] - '0') << K) + num) >> 1;
            if (!seen[num]) seen[num] = true, count--;
            if (!count) return true;
            if (i < count) return false;
        }
        return false;
    }
};
```