{x}
blog image

Check If a String Contains All Binary Codes of Size K

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

Solution Explanation for LeetCode 1461: Check If a String Contains All Binary Codes of Size K

This problem asks whether all possible binary codes of length k are substrings of a given binary string s. We'll explore two efficient solutions: using a hash table (set) and a sliding window approach.

Solution 1: Hash Table (Set)

Approach:

  1. Pre-check: If the length of s (after accounting for the k-length substrings) is less than the total number of possible binary codes of length k (2k), it's impossible for all codes to be present. Return false in this case.

  2. Generate Substrings: Iterate through s and generate all substrings of length k. Store these substrings in a set (hash table) to automatically handle duplicates.

  3. Check for Completeness: Compare the size of the set to 2k. If they are equal, all possible binary codes are present; otherwise, not all are present.

Code (Python):

class Solution:
    def hasAllCodes(self, s: str, k: int) -> bool:
        n = len(s)
        m = 1 << k  # 2**k
        if n - k + 1 < m:
            return False
        ss = {s[i:i + k] for i in range(n - k + 1)}
        return len(ss) == m

Time Complexity: O(nk) - Generating substrings takes O(nk) time in the worst case. The set operations (insertion and size check) are amortized O(1) on average.

Space Complexity: O(min(n, 2k)) - The set stores at most min(n, 2k) unique substrings.

Solution 2: Sliding Window

Approach:

This solution optimizes substring generation by using a sliding window and bit manipulation.

  1. Pre-check: Same as Solution 1.

  2. Sliding Window and Bit Manipulation:

    • Convert the initial k-length substring to an integer x.
    • Use a set to track seen integer representations of substrings.
    • Iterate through the rest of the string. In each iteration:
      • Shift the bits in x to the left by 1 (multiplying by 2).
      • Add the new bit (the next character) to the least significant bit.
      • Add the updated x to the set.

  3. Check for Completeness: Same as Solution 1.

Code (Python):

class Solution:
    def hasAllCodes(self, s: str, k: int) -> bool:
        n = len(s)
        m = 1 << k
        if n - k + 1 < m:
            return False
        ss = set()
        x = int(s[:k], 2) #convert initial substring to integer
        ss.add(x)
        for i in range(k, n):
            a = int(s[i - k]) << (k - 1) #left shift the leftmost bit out
            b = int(s[i]) #the new rightmost bit
            x = (x - a) << 1 | b #update x efficiently
            ss.add(x)
        return len(ss) == m

Time Complexity: O(n) - The sliding window iterates through the string once. Bit manipulation operations are O(1).

Space Complexity: O(min(n, 2k)) - The set stores at most min(n, 2k) unique integer representations of substrings.

Summary:

Solution 2 (sliding window) is generally preferred due to its linear time complexity, making it more efficient for larger input strings. Solution 1 is simpler to understand but less efficient for larger inputs. Both solutions use a set for efficient duplicate handling. Remember that the space complexity depends on the minimum of the string length and the total number of possible binary codes.