Input:
s ="00110110", k =2Output:
trueExplanation:
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.
There are exactly 2^k possible binary codes of length k. If we collect every distinct substring of length k from s into a set and its size equals 2^k, then every code appears.
import java.util.*;
classSolution {
publicbooleanhasAllCodes(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);
}
}
1
2
3
4
5
6
from typing import List
classSolution:
defhasAllCodes(self, s: str, k: int) -> bool:
seen = {s[i:i+k] for i in range(len(s) - k +1)}
return len(seen) == (1<< k)
1
2
3
4
5
6
7
classSolution {
funhasAllCodes(s: String, k: Int): Boolean {
val set = HashSet<String>()
for (i in0..s.length - k) set.add(s.substring(i, i + k))
returnset.size == (1 shl k)
}
}
1
2
3
4
5
6
7
8
9
10
11
12
use std::collections::HashSet;
impl Solution {
pubfnhas_all_codes(s: String, k: i32) -> bool {
let k = k asusize;
letmut set = HashSet::new();
let bytes = s.as_bytes();
for i in0..=bytes.len().saturating_sub(k) {
set.insert(&bytes[i..i+k]);
}
set.len() ==1<< k
}
}
Represent each length-k substring as an integer using bit operations (a rolling mask). This avoids allocating substring objects and runs in linear time.
import java.util.*;
classSolution {
publicbooleanhasAllCodes(String s, int k) {
if (s.length() < k) returnfalse;
Set<Integer> seen =new HashSet<>();
int mask = 0, all = (1 << k) - 1;
for (int i = 0; i < s.length(); ++i) {
mask = ((mask << 1) & all) | (s.charAt(i) -'0');
if (i >= k - 1) seen.add(mask);
}
return seen.size() == (1 << k);
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
from typing import List
classSolution:
defhasAllCodes(self, s: str, k: int) -> bool:
need =1<< k
got = set()
mask =0 all_mask = (1<< k) -1for i, ch in enumerate(s):
mask = ((mask <<1) & all_mask) | int(ch)
if i >= k -1:
got.add(mask)
return len(got) == need
1
2
3
4
5
6
7
8
9
10
11
12
13
14
classSolution {
funhasAllCodes(s: String, k: Int): Boolean {
if (s.length < k) returnfalseval need = 1 shl k
val got = HashSet<Int>()
var mask = 0val all = (1 shl k) - 1for (i in s.indices) {
mask = ((mask shl 1) and all) or (s[i] - '0')
if (i >= k - 1) got.add(mask)
}
return got.size == need
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
use std::collections::HashSet;
impl Solution {
pubfnhas_all_codes(s: String, k: i32) -> bool {
let need =1<< k;
letmut got = HashSet::new();
letmut mask =0usize;
let all = (1<< k) asusize-1;
for (i, &b) in s.as_bytes().iter().enumerate() {
mask = ((mask <<1) & all) | ((b -b'0') asusize);
if i >= (k -1) asusize { got.insert(mask); }
}
got.len() == need asusize }
}
#include<vector>#include<string>usingnamespace std;
classSolution {
public:bool hasAllCodes(const string& s, int k) {
int n = s.size();
if (n < k) return false;
int total =1<< k;
vector<char> seen(total, 0);
int mask =0;
for (int i =0; i < n; ++i) {
mask = ((mask <<1) & (total -1)) | (s[i] -'0');
if (i >= k -1) seen[mask] =1;
}
for (char b : seen) if (!b) return false;
return true;
}
};
classSolution {
publicbooleanhasAllCodes(String s, int k) {
int n = s.length(), total = 1 << k, mask = 0;
boolean[] seen =newboolean[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) returnfalse;
returntrue;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
from typing import List
classSolution:
defhasAllCodes(self, s: str, k: int) -> bool:
n = len(s)
if n < k: returnFalse total =1<< k
seen = [False] * total
mask =0for i in range(n):
mask = ((mask <<1) & (total -1)) | int(s[i])
if i >= k -1:
seen[mask] =Truereturn all(seen)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
classSolution {
funhasAllCodes(s: String, k: Int): Boolean {
val n = s.length
if (n < k) returnfalseval total = 1 shl k
val seen = BooleanArray(total)
var mask = 0for (i in0 until n) {
mask = ((mask shl 1) and (total - 1)) or (s[i] - '0')
if (i >= k - 1) seen[mask] = true }
return seen.all { it }
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
impl Solution {
pubfnhas_all_codes(s: String, k: i32) -> bool {
let n = s.len();
let k = k asusize;
if n < k { returnfalse; }
let total =1<< k;
letmut seen =vec![false; total];
letmut mask =0usize;
for (i, &b) in s.as_bytes().iter().enumerate() {
mask = ((mask <<1) & (total -1)) | ((b -b'0') asusize);
if i >= k -1 { seen[mask] =true; }
}
seen.into_iter().all(|b| b)
}
}