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 def hasAllCodes(s: str, k: int) -> bool:
3 seen = set()
4 for i in range(len(s) - k + 1):
5 substring = s[i:i+k]
6 seen.add(substring)
7 if len(seen) == 2**k:
8 return True
9 return False
10 The function utilizes a set to keep track of unique substrings of length k. Iterating over the string from index 0 to len(s)-k, each k-length substring is added to the set. If the set's size becomes 2^k, we know all binary codes of length k are present in s. The operation seen.add(substring) ensures unique tracking, while len(seen) == 2**k quickly checks the condition to return true.
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 <vector>
3 #include <string>
4
class Solution {
public:
bool hasAllCodes(std::string s, int k) {
int need = 1 << k;
std::vector<bool> seen(need, false);
int hash = 0;
int allOnes = need - 1;
for (int i = 0; i < s.size(); i++) {
hash = ((hash << 1) & allOnes) | (s[i] - '0');
if (i >= k - 1 && !seen[hash]) {
seen[hash] = true;
if (--need == 0) return true;
}
}
return false;
}
};
This C++ approach involves a boolean vector to mark seen k-length binary sequences as integers. Bit manipulation (shifts and masks) facilitates efficient updating of the hash representing these substrings. As each is checked and marked, the solution recognizes when all possible sequences have been seen.