*This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful,* *please like**this post and/or* *upvote**my solution post on Leetcode's forums.*

####
Leetcode Problem #1461 (*Medium*): Check If a String Contains All Binary Codes of Size K

####
*Description:*

*Description:*

(*Jump to*: *Solution Idea* || *Code*: *JavaScript* | *Python* | *Java* | *C++*)

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:*

*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:*

*Constraints:*

`1 <= s.length <= 5 * 10^5`

`s`

consists of`0`

's and`1`

's only.`1 <= k <= 20`

####
*Idea:*

*Idea:*

(*Jump to*: *Problem Description* || *Code*: *JavaScript* | *Python* | *Java* | *C++*)

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:*

*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:*

*Javascript Code:*

(*Jump to*: *Problem Description* || *Solution Idea*)

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

*Python Code:*

(*Jump to*: *Problem Description* || *Solution Idea*)

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

*Java Code:*

(*Jump to*: *Problem Description* || *Solution Idea*)

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

*C++ Code:*

(*Jump to*: *Problem Description* || *Solution Idea*)

```
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;
}
};
```

## Discussion (0)