Problem#
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:
1
2
3
4
5
|
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 indices 0, 1, 3 and 2 respectively.
|
Example 2:
1
2
3
4
5
|
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 3:
1
2
3
4
5
|
Input:
s = "0110", k = 2
Output:
false
Explanation: The binary code "00" is of length 2 and does not exist in the array.
|
Solution#
Method 1: Hash Set of Substrings (Recommended)#
Intuition#
We need to check if every possible binary string of length k appears as a substring in s. There are exactly 2^k such binary codes. We can use a set to collect all unique substrings of length k in s and compare the size to 2^k.
Approach#
- Iterate over all substrings of length
k in s and add them to a set.
- If the set size equals
2^k, return true; otherwise, return false.
Python#
1
2
3
4
|
class Solution:
def hasAllCodes(self, s: str, k: int) -> bool:
seen = set(s[i:i+k] for i in range(len(s)-k+1))
return len(seen) == 1 << k
|
Java#
1
2
3
4
5
6
7
8
9
10
|
import java.util.*;
class Solution {
public boolean hasAllCodes(String s, int k) {
Set<String> set = new HashSet<>();
for (int i = 0; i <= s.length() - k; i++) {
set.add(s.substring(i, i + k));
}
return set.size() == (1 << k);
}
}
|
C++#
1
2
3
4
5
6
7
8
9
10
11
12
|
#include <unordered_set>
#include <string>
using namespace std;
class Solution {
public:
bool hasAllCodes(string s, int k) {
unordered_set<string> seen;
for (int i = 0; i + k <= s.size(); ++i)
seen.insert(s.substr(i, k));
return seen.size() == (1 << k);
}
};
|
1
2
3
4
5
6
7
|
func hasAllCodes(s string, k int) bool {
seen := make(map[string]struct{})
for i := 0; i <= len(s)-k; i++ {
seen[s[i:i+k]] = struct{}{}
}
return len(seen) == 1<<k
}
|
Kotlin#
1
2
3
4
5
6
7
8
9
|
class Solution {
fun hasAllCodes(s: String, k: Int): Boolean {
val set = mutableSetOf<String>()
for (i in 0..s.length - k) {
set.add(s.substring(i, i + k))
}
return set.size == (1 shl k)
}
}
|
Rust#
1
2
3
4
5
6
7
8
9
10
11
12
|
use std::collections::HashSet;
impl Solution {
pub fn has_all_codes(s: String, k: i32) -> bool {
let k = k as usize;
let mut set = HashSet::new();
let bytes = s.as_bytes();
for i in 0..=bytes.len().saturating_sub(k) {
set.insert(&bytes[i..i+k]);
}
set.len() == 1 << k
}
}
|
Complexity#
- Time: O(n * k), where n = length of s
- Space: O(2^k * k)
Method 2: Rolling Hash (Optimized for Large k)#
Intuition#
Instead of storing substrings, we can use a rolling hash to store integer representations of the binary codes.
Approach#
- Use a sliding window and bit manipulation to represent each substring as an integer.
- Store each integer in a set.
- Compare the set size to
2^k.
Python#
1
2
3
4
5
6
7
8
9
10
|
class Solution:
def hasAllCodes(self, s: str, k: int) -> bool:
need = 1 << k
got = set()
hash_val = 0
for i, c in enumerate(s):
hash_val = ((hash_val << 1) & ((1 << k) - 1)) | int(c)
if i >= k - 1:
got.add(hash_val)
return len(got) == need
|
Complexity#
Method 3: Bitmask Optimization (Space Efficient, for Large k)#
Intuition#
If k is not too large (e.g., k <= 20), we can use a boolean array of size 2^k to track which binary codes have been seen, using bitmasking for fast lookup and update.
Approach#
- Initialize a boolean array of size
2^k.
- Use a rolling bitmask to represent the current substring as an integer.
- Mark the corresponding index as seen.
- If all indices are seen, return
true.
Python#
1
2
3
4
5
6
7
8
9
10
11
12
|
class Solution:
def hasAllCodes(self, s: str, k: int) -> bool:
n = len(s)
if n < k: return False
total = 1 << k
seen = [False] * total
mask = 0
for i in range(n):
mask = ((mask << 1) & (total - 1)) | int(s[i])
if i >= k - 1:
seen[mask] = True
return all(seen)
|
Java#
1
2
3
4
5
6
7
8
9
10
11
12
|
class Solution {
public boolean hasAllCodes(String s, int k) {
int n = s.length(), total = 1 << k, mask = 0;
boolean[] seen = new boolean[total];
for (int i = 0; i < n; ++i) {
mask = ((mask << 1) & (total - 1)) | (s.charAt(i) - '0');
if (i >= k - 1) seen[mask] = true;
}
for (boolean b : seen) if (!b) return false;
return true;
}
}
|
C++#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
#include <vector>
#include <string>
using namespace std;
class Solution {
public:
bool hasAllCodes(string s, int k) {
int n = s.size(), total = 1 << k, mask = 0;
vector<bool> seen(total, false);
for (int i = 0; i < n; ++i) {
mask = ((mask << 1) & (total - 1)) | (s[i] - '0');
if (i >= k - 1) seen[mask] = true;
}
for (bool b : seen) if (!b) return false;
return true;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
func hasAllCodes(s string, k int) bool {
n, total, mask := len(s), 1<<k, 0
seen := make([]bool, total)
for i := 0; i < n; i++ {
mask = ((mask << 1) & (total - 1)) | int(s[i]-'0')
if i >= k-1 {
seen[mask] = true
}
}
for _, b := range seen {
if !b {
return false
}
}
return true
}
|
Kotlin#
1
2
3
4
5
6
7
8
9
10
11
12
13
|
class Solution {
fun hasAllCodes(s: String, k: Int): Boolean {
val n = s.length
val total = 1 shl k
val seen = BooleanArray(total)
var mask = 0
for (i in 0 until n) {
mask = ((mask shl 1) and (total - 1)) or (s[i] - '0')
if (i >= k - 1) seen[mask] = true
}
return seen.all { it }
}
}
|
Rust#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
impl Solution {
pub fn has_all_codes(s: String, k: i32) -> bool {
let n = s.len();
let k = k as usize;
let total = 1 << k;
let mut seen = vec![false; total];
let bytes = s.as_bytes();
let mut mask = 0;
for i in 0..n {
mask = ((mask << 1) & (total - 1)) | (bytes[i] - b'0') as usize;
if i + 1 >= k {
seen[mask] = true;
}
}
seen.iter().all(|&b| b)
}
}
|
Complexity#