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:

Example 2:

Example 3:

Example 4:

Example 5:

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.

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.

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.

Software Engineer. Find me @ www.linkedin.com/in/annamariya-jt