Problem Description

Given a binary string s and an integer k, determine if every possible binary code of length k exists as a substring in s.
A binary code of length k is any string of k characters where each character is either '0' or '1'. There are exactly 2^k such codes.
Constraints:

• The string s consists only of characters '0' and '1'.
• 1 <= s.length <= 5 * 10^5
• 1 <= k <= 20

Thought Process

To solve this problem, let's first consider what is being asked:

• We need to check if all possible binary codes of length k appear as substrings in s.
• For example, if k=2, the codes are '00', '01', '10', '11'.
• Brute-force would mean generating all possible codes and checking if each one appears in s—but this is inefficient for large k and s.
• Instead, we can scan s once, extract every substring of length k, and keep track of which codes we've seen.
• If we've seen all 2^k codes, we return True; otherwise, False.

Solution Approach

Let's break down the algorithm step by step:

1. Initialize a set: Use a set to keep track of all unique substrings of length k found in s. Sets are used because they allow for O(1) insert and lookup times.
2. Iterate through the string: For each position i from 0 to len(s) - k, extract the substring s[i:i+k] and add it to the set.
3. Early stopping: Since there are 2^k possible codes, if the set reaches this size, we can immediately return True.
4. Final check: After iterating, check if the set size is exactly 2^k. If so, return True; otherwise, False.

Why use a set? Because we only care about unique codes, and checking if a code is already seen is fast with a set.

Optimization: Instead of storing substrings, we can also store integer representations (by converting binary substrings to integers), which can be more memory efficient, especially for large k.

Example Walkthrough

Example:
s = "00110110", k = 2
All binary codes of length 2: '00', '01', '10', '11'
Let's extract all substrings of length 2:

• s[0:2] = "00" → add to set
• s[1:3] = "01" → add to set
• s[2:4] = "11" → add to set
• s[3:5] = "10" → add to set
• s[4:6] = "01" → already in set
• s[5:7] = "11" → already in set
• s[6:8] = "10" → already in set

Time and Space Complexity

Brute-force approach:

• Generate all 2^k codes and check each one in s (using substring search):
• Time: O((2^k) * n), where n is length of s
• Space: O(1) if not storing anything extra

• We scan s once, extracting all n - k + 1 substrings of length k.
• Time: O(n), since each substring extraction and set operation is O(1)
• Space: O(2^k), for storing all possible codes in the set

Summary

In this problem, we efficiently determine if a string contains all possible binary codes of a given length by sliding a window of size k over the string and collecting unique substrings in a set. The approach leverages the properties of sets for fast lookups and uniqueness, and stops early if all codes are found. This is both time and space efficient for the given constraints, making it an elegant solution to a potentially challenging combinatorial problem.

Code Implementation

class Solution:
    def hasAllCodes(self, s: str, k: int) -> bool:
        seen = set()
        total = 1 << k  # 2^k
        for i in range(len(s) - k + 1):
            code = s[i:i+k]
            seen.add(code)
            if len(seen) == total:
                return True
        return len(seen) == total
      

class Solution {
public:
    bool hasAllCodes(string s, int k) {
        unordered_set<string> seen;
        int total = 1 << k;
        for (int i = 0; i <= s.size() - k; ++i) {
            seen.insert(s.substr(i, k));
            if (seen.size() == total)
                return true;
        }
        return seen.size() == total;
    }
};
      

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

var hasAllCodes = function(s, k) {
    const seen = new Set();
    const total = 1 << k;
    for (let i = 0; i <= s.length - k; i++) {
        seen.add(s.substring(i, i + k));
        if (seen.size === total)
            return true;
    }
    return seen.size === total;
};