Check If a String Contains All Binary Codes of Size K

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
6
7
8
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
6
7
8
Input:
s = "0110", k = 1

Output:
true

Explanation:
The binary codes of length 1 are "0" and "1"; both exist as substrings.

Example 3

1
2
3
4
5
6
7
8
Input:
s = "0110", k = 2

Output:
false

Explanation:
The binary code "00" of length 2 does not exist in the string.

Solution

Method 1 - Hash Set of Substrings (Recommended)

Intuition

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.

Approach

Iterate over all length-k windows in s and insert each substring into a set.
If the set size equals 2^k, return true; otherwise return false.

Code

 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(const string& s, int k) {
    unordered_set<string> seen;
    for (int i = 0; i + k <= (int)s.size(); ++i) seen.insert(s.substr(i, k));
    return static_cast<int>(seen.size()) == (1 << k);
  }
};

1
2
3
4
5
6
7
8
9
package main

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
}

1
2
3
4
5
6
7
8
9
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);
  }
}

1
2
3
4
5
6
from typing import List

class Solution:
  def hasAllCodes(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
class Solution {
  fun hasAllCodes(s: String, k: Int): Boolean {
    val set = HashSet<String>()
    for (i in 0..s.length - k) set.add(s.substring(i, i + k))
    return set.size == (1 shl k)
  }
}

 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
  }
}

1
2
3
4
5
6
7
export class Solution {
  hasAllCodes(s: string, k: number): boolean {
    const seen = new Set<string>();
    for (let i = 0; i + k <= s.length; i++) seen.add(s.slice(i, i + k));
    return seen.size === (1 << k);
  }
}

Complexity

⏰ Time complexity: O(n * k) – We build each length-k substring in O(k) and there are O(n) windows.
🧺 Space complexity: O(2^k * k) – We may store up to 2^k substrings of length k in the set.

Method 2 - Rolling Hash / Bitmask (Optimized)

Intuition

Represent each length-k substring as an integer using bit operations (a rolling mask). This avoids allocating substring objects and runs in linear time.

Approach

Maintain a rolling integer mask of the last k bits.
Slide through s, updating mask = ((mask << 1) & ((1<<k)-1)) | bit.
Insert mask into a set (or mark in a boolean array). At the end check that we have 2^k distinct masks.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
#include <vector>
#include <string>
#include <unordered_set>
using namespace std;

class Solution {
 public:
  bool hasAllCodes(const string& s, int k) {
    if ((int)s.size() < k) return false;
    unordered_set<int> seen;
    int mask = 0, all = (1 << k) - 1;
    for (int i = 0; i < (int)s.size(); ++i) {
      mask = ((mask << 1) & all) | (s[i] - '0');
      if (i >= k - 1) seen.insert(mask);
    }
    return static_cast<int>(seen.size()) == (1 << k);
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
package main

func hasAllCodes(s string, k int) bool {
    if len(s) < k { return false }
    need := 1 << k
    got := make(map[int]struct{})
    mask := 0
    all := (1 << k) - 1
    for i := 0; i < len(s); i++ {
        mask = ((mask << 1) & all) | int(s[i]-'0')
        if i >= k-1 {
            got[mask] = struct{}{}
        }
    }
    return len(got) == need
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
import java.util.*;

class Solution {
  public boolean hasAllCodes(String s, int k) {
    if (s.length() < k) return false;
    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

class Solution:
  def hasAllCodes(self, s: str, k: int) -> bool:
    need = 1 << k
    got = set()
    mask = 0
    all_mask = (1 << k) - 1
    for 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
class Solution {
  fun hasAllCodes(s: String, k: Int): Boolean {
    if (s.length < k) return false
    val need = 1 shl k
    val got = HashSet<Int>()
    var mask = 0
    val all = (1 shl k) - 1
    for (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 {
  pub fn has_all_codes(s: String, k: i32) -> bool {
    let need = 1 << k;
    let mut got = HashSet::new();
    let mut mask = 0usize;
    let all = (1 << k) as usize - 1;
    for (i, &b) in s.as_bytes().iter().enumerate() {
      mask = ((mask << 1) & all) | ((b - b'0') as usize);
      if i >= (k - 1) as usize { got.insert(mask); }
    }
    got.len() == need as usize
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
export class Solution {
  hasAllCodes(s: string, k: number): boolean {
    if (s.length < k) return false;
    const need = 1 << k;
    const got = new Set<number>();
    let mask = 0;
    const all = (1 << k) - 1;
    for (let i = 0; i < s.length; i++) {
      mask = ((mask << 1) & all) | (s.charCodeAt(i) - 48);
      if (i >= k - 1) got.add(mask);
    }
    return got.size === need;
  }
}

Complexity

⏰ Time complexity: O(n) – A single pass with O(1) work per character.
🧺 Space complexity: O(2^k) – We store up to 2^k distinct integer masks.

Method 3 - Bitmask Array (Space-optimized boolean array)

Intuition

If k is reasonably small (e.g., k <= 20), a boolean array of size 2^k is more memory- and time-efficient than a hash set.

Approach

Use a boolean array seen of size 2^k initialized to false.
Use a rolling mask and mark seen[mask] = true when a window is complete.
At the end, check that every entry in seen is true.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
#include <vector>
#include <string>
using namespace std;

class Solution {
 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;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
package main

func hasAllCodes(s string, k int) bool {
    n := len(s)
    if n < k { return false }
    total := 1 << k
    seen := make([]bool, total)
    mask := 0
    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
}

 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;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
from typing import List

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)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
  fun hasAllCodes(s: String, k: Int): Boolean {
    val n = s.length
    if (n < k) return false
    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 }
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
impl Solution {
  pub fn has_all_codes(s: String, k: i32) -> bool {
    let n = s.len();
    let k = k as usize;
    if n < k { return false; }
    let total = 1 << k;
    let mut seen = vec![false; total];
    let mut mask = 0usize;
    for (i, &b) in s.as_bytes().iter().enumerate() {
      mask = ((mask << 1) & (total - 1)) | ((b - b'0') as usize);
      if i >= k - 1 { seen[mask] = true; }
    }
    seen.into_iter().all(|b| b)
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
export class Solution {
  hasAllCodes(s: string, k: number): boolean {
    const n = s.length;
    if (n < k) return false;
    const total = 1 << k;
    const seen = new Array<boolean>(total).fill(false);
    let mask = 0;
    for (let i = 0; i < n; i++) {
      mask = ((mask << 1) & (total - 1)) | (s.charCodeAt(i) - 48);
      if (i >= k - 1) seen[mask] = true;
    }
    return seen.every(Boolean);
  }
}

Complexity

⏰ Time complexity: O(n) – Single pass over the input string.
🧺 Space complexity: O(2^k) – The boolean array size is 2^k.

Problem#

Examples#

Example 1#

Example 2#

Example 3#

Solution#

Method 1 - Hash Set of Substrings (Recommended)#

Intuition#

Approach#

Code#

Complexity#

Method 2 - Rolling Hash / Bitmask (Optimized)#

Intuition#

Approach#

Code#

Complexity#

Method 3 - Bitmask Array (Space-optimized boolean array)#

Intuition#

Approach#

Code#

Complexity#

Problem

Examples

Example 1

Example 2

Example 3

Solution

Method 1 - Hash Set of Substrings (Recommended)

Intuition

Approach

Code

Complexity

Method 2 - Rolling Hash / Bitmask (Optimized)

Intuition

Approach

Code

Complexity

Method 3 - Bitmask Array (Space-optimized boolean array)

Intuition

Approach

Code

Complexity