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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Check If a String Contains All Binary Codes of Size K

Difficulty: Medium

Problem Description

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.

Key Insights

  • The total number of unique binary codes of length k is 2^k.
  • We can extract all substrings of length k from the string s.
  • A set can be used to track the unique substrings found.
  • If the size of the set equals 2^k, then we have found all possible binary codes.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the string s. Space Complexity: O(1) for the set, since the maximum size is limited to 2^k.

Solution

To solve this problem, we can utilize a sliding window approach to extract all possible substrings of length k from the string s. We will store these substrings in a set to filter out duplicates automatically. After processing the string, we will compare the size of the set with the total number of unique binary codes, which is 2^k. If they match, it means all binary codes of length k are present in s.

Code Solutions

def hasAllCodes(s: str, k: int) -> bool:
    required_codes = 1 << k  # 2^k
    found_codes = set()

    for i in range(len(s) - k + 1):
        found_codes.add(s[i:i + k])
        if len(found_codes) == required_codes:
            return True

    return len(found_codes) == required_codes
← Back to All Questions