Sponsored
Sponsored
This approach uses a set to store all unique substrings of length k encountered in s. By sliding a window of size k across the string, we add each substring to the set. If the set size equals 2^k, return true because all possible binary strings of length k are present. Otherwise, return false.
Time Complexity: O(n * k) where n is the length of the string,
Space Complexity: O(min(2^k, n)), primarily due to the set storing at most 2^k elements.
1
2 function hasAllCodes(s, k) {
3 const seen = new Set();
4 for (let i = 0; i <= s.length - k; i++) {
5 const substring = s.substring(i, i + k);
6 seen.add(substring);
7 if (seen.size === 2 ** k) {
8 return true;
9 }
10 }
11 return false;
12 }
13 This function uses a Set in JavaScript to handle unique substrings. By extracting substrings via s.substring(i, i + k), we add each to our set. Thus, it checks seen.size === 2 ** k to determine if all possible codes are present, promptly returning true in that scenario.
This approach improves efficiency by using bit manipulation instead of storing full substrings. Treat the k-length binary strings as numbers and update a rolling number using bitmasking while sliding over string s. This can detect all variations without explicitly storing them.
Time Complexity: O(n),
Space Complexity: O(2^k), primarily determined by the boolean tracking array.
1
2 #include <stdbool.h>
The C solution utilizes a boolean array to represent the presence of each binary code of length k. By treating binary codes as integers and updating a rolling hash (a bitmask method shifting left and masking), it determines uniqueness with minimal space. Each k-length sequence is translated into this integer representation, tracked via the boolean array.