# Check If a String Contains All Binary Codes of Size K
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/check-if-a-string-contains-all-binary-codes-of-size-k)
Canonical: https://scaleengineer.com/dsa/problems/check-if-a-string-contains-all-binary-codes-of-size-k
**Patterns:** [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation), [Rolling Hash](https://scaleengineer.com/dsa/patterns/rolling-hash), [Hash Function](https://scaleengineer.com/dsa/patterns/hash-function)
**Algorithms:** [Bloom Filter](https://scaleengineer.com/algorithms/bloom-filter)
**Data structures:** Hash Table, String
---
## 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`.

**Example 1:**

**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:**

**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:**

**Input:** s = "0110", k = 2
**Output:** false
**Explanation:** The binary code "00" is of length 2 and does not exist in the array.

**Constraints:**

* `1 <= s.length <= 5 * 105`
* `s[i]` is either `'0'` or `'1'`.
* `1 <= k <= 20`

# Approaches
## Brute-Force: Generate and Check
This approach is a straightforward brute-force method. It works by first generating every possible binary code of length `k`. Then, for each of these `2^k` codes, it performs a search within the input string `s` to check for its presence. While simple to conceptualize, its performance is very poor due to the nested operations of generation and searching.
**Time:** O(2^k * N * k), where `N` is the length of `s`. We generate `2^k` codes. For each code, `s.contains()` can take up to `O(N * k)` time in the worst case. This complexity is too high for the given constraints. · **Space:** O(k). This space is used to temporarily store each binary code string of length `k` that is generated.
**Pros:** Simple to understand and implement the logic.
**Cons:** Extremely inefficient and slow, especially for larger values of `k` and `s.length()`.; The time complexity makes it infeasible for the given constraints, leading to a 'Time Limit Exceeded' error.
### Explanation
The core idea is to exhaustively check for every single possibility. We know there are `2^k` unique binary codes of length `k`. We can generate them by iterating from integer `0` to `2^k - 1` and converting each integer to its binary string form, ensuring each string is padded with leading zeros to have a length of exactly `k`. For example, if `k=3` and `i=1`, we generate the string "001". After generating a code, we use a standard library function like `s.contains()` to search for it in the input string. If at any point a code is not found, we can stop and return `false`. If we successfully iterate through all `2^k` codes and find each one in `s`, we return `true`.

```java
class Solution {
    public boolean hasAllCodes(String s, int k) {
        int totalCodes = 1 << k; // This is 2^k
        for (int i = 0; i < totalCodes; i++) {
            String binaryCode = Integer.toBinaryString(i);
            // Create a format string like "%03s" if k=3 to pad with zeros
            String format = "%" + k + "s";
            String paddedCode = String.format(format, binaryCode).replace(' ', '0');
            
            if (!s.contains(paddedCode)) {
                return false;
            }
        }
        return true;
    }
}
```
### Algorithm
- Calculate the total number of required codes, which is `2^k`.
- Iterate through all numbers from `0` to `2^k - 1`.
- For each number, convert it to its `k`-bit binary string representation. This may require padding with leading zeros.
- For each generated binary string, check if it exists as a substring within the input string `s`.
- If any binary code is not found in `s`, we can immediately conclude that not all codes are present and return `false`.
- If the loop completes without finding any missing codes, it means all `2^k` codes were found, and we return `true`.

## Using a HashSet of Substrings
A more practical approach is to iterate through the input string `s` and find all unique substrings of length `k`. We can use a `HashSet` to keep track of the substrings we've encountered. By the end of the iteration, if the number of unique substrings in our set is equal to `2^k`, we know that all possible binary codes were present in the string.
**Time:** O(N * k), where `N` is the length of `s`. The loop runs `N - k + 1` times. Inside the loop, `substring()` takes `O(k)` time, and adding it to the `HashSet` also takes `O(k)` on average (for hashing and equality checks). · **Space:** O(2^k * k). In the worst case, the `HashSet` stores `2^k` unique strings, each of length `k`.
**Pros:** Significantly more efficient than the brute-force approach.; Relatively easy to implement and understand.; Passes the time limits for the given constraints.
**Cons:** Creating a new substring in each iteration can be inefficient for very long strings.; The space complexity depends on `k` and can be large if `k` is close to 20, as it stores `2^k` strings of length `k`.
### Explanation
Instead of generating codes and searching for them, this method reverses the process. We slide a window of size `k` over the string `s`. At each position, we extract the `k`-length substring and insert it into a `HashSet<String>`. The `HashSet` provides an efficient way to store only the unique substrings. After iterating through all possible starting positions in `s`, we are left with a set containing every unique `k`-length binary code that appears in `s`. The final step is to check if the size of this set is equal to `2^k`. If it is, we have found all possible codes. This avoids the costly search operation of the brute-force method.

```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public boolean hasAllCodes(String s, int k) {
        int n = s.length();
        // It's impossible to have 2^k substrings if the string is too short.
        if (n < k) {
            return false;
        }
        
        Set<String> foundCodes = new HashSet<>();
        for (int i = 0; i <= n - k; i++) {
            foundCodes.add(s.substring(i, i + k));
        }
        
        return foundCodes.size() == (1 << k);
    }
}
```
### Algorithm
- Create a `HashSet<String>` to store unique substrings.
- Calculate the total number of codes required, `requiredCount = 2^k`.
- Iterate through the input string `s` from index `i = 0` up to `s.length() - k`.
- In each iteration, extract the substring of length `k` starting at `i` (i.e., `s.substring(i, i + k)`).
- Add this substring to the `HashSet`. The set will automatically handle duplicates.
- After the loop finishes, compare the size of the `HashSet` with `requiredCount`.
- If `hashSet.size() == requiredCount`, it means all possible codes were found, so return `true`. Otherwise, return `false`.

## Optimized Sliding Window with Rolling Hash
The most optimal solution uses a sliding window combined with a rolling hash. Instead of working with strings, we can represent each binary code of length `k` as an integer. This allows for a very fast, `O(1)` update of the code's value as we slide the window one position at a time. We use a boolean array or a `HashSet` of integers to keep track of the codes we have found, which is more memory-efficient than storing strings.
**Time:** O(N), where `N` is the length of `s`. The initial hash calculation takes `O(k)`, and the subsequent loop runs `N-k` times with `O(1)` work inside. Thus, the total time is `O(k + N - k) = O(N)`. · **Space:** O(2^k). We need a data structure (a boolean array in this case) to keep track of the `2^k` possible codes.
**Pros:** Optimal time complexity, as it processes the string in a single pass.; Memory efficient, as it stores integers or booleans instead of strings.; Avoids the overhead of repeated substring creation and hashing.
**Cons:** The rolling hash logic is slightly more complex to implement compared to the substring approach.
### Explanation
This approach enhances the sliding window concept by avoiding the overhead of creating and hashing new string objects in each step. We treat each `k`-length binary substring as a `k`-bit integer. First, we compute the integer value for the initial window of `k` characters. Then, we iterate through the rest of the string. In each step, we efficiently calculate the integer value of the new window by using the value from the previous window. This is done by shifting the old value one bit to the left (which discards the most significant bit's old contribution), and then adding the new character's bit value as the new least significant bit. A bitmask is used to ensure the integer value stays within `k` bits. We use a boolean array `seen` of size `2^k` to mark which integer codes have been encountered. If we find all `2^k` codes, we return `true`.

```java
class Solution {
    public boolean hasAllCodes(String s, int k) {
        int n = s.length();
        int totalCodes = 1 << k;

        if (n < k) {
            return false;
        }

        boolean[] seen = new boolean[totalCodes];
        int foundCount = 0;
        int currentHash = 0;
        int mask = totalCodes - 1; // A mask of k ones, e.g., k=3 -> mask=7 (111)

        // Calculate hash for the first window of size k
        for (int i = 0; i < k; i++) {
            currentHash = (currentHash << 1) | (s.charAt(i) - '0');
        }
        seen[currentHash] = true;
        foundCount = 1;

        // Slide the window through the rest of the string
        for (int i = k; i < n; i++) {
            // Update hash using rolling hash technique
            currentHash = ((currentHash << 1) & mask) | (s.charAt(i) - '0');
            
            if (!seen[currentHash]) {
                seen[currentHash] = true;
                foundCount++;
            }
        }
        
        return foundCount == totalCodes;
    }
}
```
### Algorithm
- Calculate `totalCodes = 2^k`. Check if `s.length()` is sufficient to contain all codes. If `s.length() - k + 1 < totalCodes`, return `false`.
- Create a `boolean` array `seen` of size `totalCodes` initialized to `false`.
- Calculate the integer value (`hash`) for the first `k`-length substring of `s`.
- Mark this first hash as seen: `seen[hash] = true`, and initialize a counter `foundCount = 1`.
- Use a rolling hash technique: iterate from `i = k` to `s.length() - 1`.
  - Update the hash in `O(1)` time: shift the previous hash left by one bit, mask it to `k` bits, and OR it with the new bit from `s.charAt(i)`.
  - If the new hash has not been seen before (`!seen[newHash]`):
    - Mark it as seen: `seen[newHash] = true`.
    - Increment `foundCount`.
- After the loop, return `true` if `foundCount == totalCodes`, and `false` otherwise.

# Solutions
### Java

```java
class Solution {
public
  boolean hasAllCodes(String s, int k) {
    Set<String> ss = new HashSet<>();
    for (int i = 0; i < s.length() - k + 1; ++i) {
      ss.add(s.substring(i, i + k));
    }
    return ss.size() == 1 << k;
  }
}

```

### CPP

```cpp
class Solution {
public:
  bool hasAllCodes(string s, int k) {
    unordered_set<string> ss;
    for (int i = 0; i + k <= s.size(); ++i) {
      ss.insert(move(s.substr(i, k)));
    }
    return ss.size() == 1 << k;
  }
};

```

### Python

```python
class Solution:
    def hasAllCodes(self, s: str, k: int) -> bool: ss = {s[i: i + k] for i in range(len(s) - k + 1)} return len(ss) == 1 << k

```