We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Check If a String Contains All Binary Codes of Size K

Number: 1557

Difficulty: Medium

Paid? No

Companies: Google

Problem Description

Given a binary string s and an integer k, determine if every possible binary code of length k appears as a substring in s.

Key Insights

  • There are 2^k possible binary codes of length k.
  • A sliding window (or rolling hash) technique can be used to efficiently traverse s and extract all substrings of length k.
  • Using bit manipulation minimizes the cost of substring extraction by representing each k-length substring as an integer.
  • Early termination is possible if s is too short to contain all the required substrings.

Space and Time Complexity

Time Complexity: O(n), where n is the length of s. Space Complexity: O(2^k), for storing the unique substrings seen.

Solution

We use a sliding window approach combined with bit manipulation to efficiently compute the integer value of each k-length substring. First, check if the length of s is sufficient, because there must be at least 2^k different substrings of length k. We initialize a set to store the unique integer representations of the substrings. As we iterate through s, we update our rolling value by shifting left, adding the current bit, and applying a bitmask to keep only k bits. Once we have processed a complete window (i.e., when index >= k - 1), we add the rolling value to the set. Finally, if the set’s size equals 2^k, we return true; otherwise, false.

Code Solutions

# Python solution with inline comments

def hasAllCodes(s: str, k: int) -> bool:
    # total number of unique codes needed
    total_codes = 1 << k  # equivalent to 2^k
    # if s is too short, immediately return False
    if len(s) < k:
        return False

    seen = set()  # store the integer representations of substrings
    curr = 0     # rolling value for the current window
    mask = total_codes - 1  # mask with last k bits set to 1

    # iterate over the string
    for i in range(len(s)):
        # update the rolling value: left shift by 1 bit, add current bit, and apply mask
        curr = ((curr << 1) & mask) | (ord(s[i]) - ord('0'))
        
        # when we have a complete window, add to the set
        if i >= k - 1:
            seen.add(curr)
            # early exit if all codes are found
            if len(seen) == total_codes:
                return True

    return len(seen) == total_codes

# Example test
print(hasAllCodes("00110110", 2))  # Output: True
← Back to All Questions