Check If A String Contains All Binary Codes Of Size K - Leetcode Solution

Problem statement:

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.

Solution:

To solve this problem, we can use a sliding window approach. We can create a set of all possible binary codes of length k (i.e., all numbers from 0 to 2^k - 1 represented in binary form). Then, we can slide a window of length k through the string S, and for each window, we can check if its binary representation is present in the set of all binary codes of length k. If yes, then we remove it from the set. Finally, if there are no binary codes left in the set, then we can return true, else return false.

Let's see the implementation of this solution in Python:

def hasAllCodes(s: str, k: int) -> bool: binary_codes = set() # Generating all binary codes of length k for num in range(2**k): binary_codes.add(bin(num)[2:].zfill(k))

# Sliding window approach
for i in range(len(s) - k + 1):
    code = s[i:i+k]
    if code in binary_codes:
        binary_codes.remove(code)
    if not binary_codes:
        return True
return False

In the above implementation, we first create a set binary_codes that contains all possible binary codes of length k. We generate these codes using a loop that generates all numbers from 0 to 2^k - 1 and converts them to binary form using the bin() function. Finally, we add them to the set after trimming the initial two characters of the binary representation (i.e., '0b') and padding with leading zeroes to make the length equal to k.

Next, we slide a window of length k through the string s using a loop that runs from 0 to len(s) - k. For each window, we check if its binary representation is present in the binary_codes set, and if yes, we remove it from the set. If after processing all windows there are no elements left in the binary_codes set, then we can return True, else we return False.

The time complexity of this solution is O(n * k), where n is the length of the string s. The space complexity is O(2^k) to hold all possible binary codes of length k in the set binary_codes.

1