Solution: Check If a String Contains All Binary Codes of Size K

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:

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

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:

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

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:

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

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

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

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