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 import java.util.HashSet;
3
4 public class Solution {
5 public boolean hasAllCodes(String s, int k) {
6 HashSet<String> seen = new HashSet<>();
7 for (int i = 0; i <= s.length() - k; i++) {
8 String sub = s.substring(i, i + k);
9 seen.add(sub);
10 if (seen.size() == (1 << k)) {
11 return true;
12 }
13 }
14 return false;
15 }
16 }
17 The Java solution capitalizes on a HashSet to store unique k-length substrings from s. The loop processes substrings from index 0 to [len(s) - k]. seen.add(sub) includes new unique entries, while its size check against (1 << k) (which equals 2^k) confirms whether all codes have been encountered.
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 using System;
3
4 public class Solution {
public bool HasAllCodes(string s, int k) {
int need = 1 << k;
bool[] seen = new bool[need];
int hash = 0;
int allOnes = need - 1;
for (int i = 0; i < s.Length; i++) {
hash = ((hash << 1) & allOnes) | (s[i] - '0');
if (i >= k - 1 && !seen[hash]) {
seen[hash] = true;
if (--need == 0) return true;
}
}
return false;
}
}
The C# solution employs a fixed-size boolean array indexed by integers representing binary substrings. Hash updates occur via bit manipulation—specifically, shifting left and combining—thus allowing new sequence detection and marking without storing full substrings.