Check If a String Contains All Binary Codes of Size K — Day 95(Python)

Photo by Alexander Sinn on Unsplash

Today’s question is from Leetcode’s Daily coding Challenge- March Edition. Let us look into the problem statement.

1461. 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 indicies 0, 1, 3 and 2 respectively.

Example 2:

Input: s = "00110", k = 2
Output: true

Example 3:

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 4:

Input: s = "0110", k = 2
Output: false
Explanation: The binary code "00" is of length 2 and doesn't exist in the array.

Example 5:

Input: s = "0000000001011100", k = 4
Output: false

Constraints:

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

We are given a string that contains two characters i.e. “1” and “0”. We are also given a number “K”. We need to check if all the binary codes of size K can be formed using the substrings from the input string.

To solve this problem, as a first step we would need to make a list of all binary codes that can be formed using the substrings from the input string. We need to keep in mind that the substrings can be repeated, hence we will be taking only the distinct substrings. Let us look at how we can do it programmatically.

all_substring = set()
for i in range(len(s)-k+1):
    all_substring.add(s[i:i+k])

What do we do next? We know our substrings will contain only two characters, either 1 or 0. And the size of substrings is “K”. This means we need to have 2^K substrings. Therefore we would just check if the number of substrings in the set of substrings is equal to 2^K. If yes, we return True else False.

class Solution:
    def hasAllCodes(self, s: str, k: int) -> bool:
        all_substring = set()
        for i in range(len(s)-k+1):
            all_substring.add(s[i:i+k])
        return True if len(all_substring) == pow(2,k)  else False

Complexity analysis.

Time Complexity

The time required to create substrings is O(NK). Hence time complexity is O(NK).

Space Complexity

The space complexity is O(2^K) since we are storing the substrings in a set.