This content originally appeared on DEV Community and was authored by seanpgallivan
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
sand an integerk.Return
Trueif every binary code of lengthkis a substring ofs. Otherwise, returnFalse.
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^5sconsists of0's and1'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;
}
};
This content originally appeared on DEV Community and was authored by seanpgallivan
seanpgallivan | Sciencx (2021-03-12T11:00:28+00:00) Solution: Check If a String Contains All Binary Codes of Size K. Retrieved from https://www.scien.cx/2021/03/12/solution-check-if-a-string-contains-all-binary-codes-of-size-k/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.