Check If A String Contains All Binary Codes Of Size K [Python]

Welcome to another coding session!

Today, we're going to tackle the LeetCode problem titled Check If A String Contains All Binary Codes Of Size K We'll provide you with a step-by-step Python solution for this problem.

If you're a beginner or someone looking to enhance your algorithmic skills, you've come to the right place.

Problem Overview

The problem is as follows: Given a binary string s and an integer k, we need to determine if every binary code of length k is a substring of the given string s.

If every binary code of length k is present in s, we return True; otherwise, we return False.

Let's illustrate this problem with a few examples.

Example 1:

Input:
– s = "00110110"
– k = 2

Output:
– True

Explanation:
– For this input, we're looking for binary codes of length 2.
– The binary codes of length 2 are "00," "01," "10," and "11."
– All of these binary codes can be found as substrings at indices 0, 1, 3, and 2, respectively, in the string s.
– Since all the binary codes are present, we return True.

Example 2:

Input:
– s = "0110"
– k = 1

Output:
– True

Explanation:
– In this case, we are looking for binary codes of length 1.
– The binary codes of length 1 are "0" and "1."
– It's evident that both of these codes exist as substrings in the string s.
– So, we return True.

Example 3:

Input:
– s = "0110"
– k = 2

Output:
– False

Explanation:
– We are searching for binary codes of length 2.
– However, in this string, the binary code "00" is of length 2 and does not exist as a substring.
– Hence, we return False.

Constraints:

• 1 <= s.length <= 5 * 105
• Each character in s is either '0' or '1'.
• 1 <= k <= 20

Now that we have a clear understanding of the problem, let's move on to the solution.

Efficient Python Code Solution

We will provide an efficient Python solution to this problem.

Here's the code:

def hasAllCodes(s: str, k: int) -> bool:
    # Create a set to store unique binary codes of size k.

code_set = set()

    # Iterate through every possible starting position in the string.

for i in range(len(s) - k + 1):
        # Check if we can create a substring of size k starting at position i.
        # This ensures there are at least k - 1 characters after position i.

if s[i : i + k] not in code_set:
            # Add the unique code to the set.

code_set.add(s[i : i + k])

    # If the number of unique binary codes is equal to 2^k, return True; otherwise, return False.

return len(code_set) == 2**k

Let's break down the code step by step.

• We start by creating a set called code_set.

This set will store the unique binary codes of size k that we find in the string s.

• Next, we iterate through every possible starting position in the string s.

We use a for loop to go from index 0 to the index that leaves at least k - 1 characters after it.

This ensures that we can create a substring of size k starting at that position.

• Within the loop, we check if the current substring of size k (from s[i : i + k]) is not already in the code_set.

If it's not in the set, we add it to the set.

This ensures that we only count unique binary codes.

• After processing all possible substrings, we check if the number of unique binary codes in the set (len(code_set)) is equal to 2^k.

If it is, we return True, indicating that all binary codes of size k are present in the string s.

Otherwise, we return False.

This solution is efficient and has a time complexity of O(n * k), where n is the length of the string s and k is the given integer.

Time and Space Complexity

Now, let's discuss the time and space complexity of our efficient solution.

• Time Complexity: Our solution has a time complexity of O(n * k), where n is the length of the input string s, and k is the integer representing the binary code length we are searching for.

We iterate through the string once, and for each iteration, we create a substring of length k.

Therefore, the time complexity is linear with respect to the length of the string and the binary code size.

• Space Complexity: The space complexity is O(2^k), as we are using a set, code_set, to store unique binary codes of size k.

In the worst case, there could be 2^k unique binary codes of that size.

Additionally, we use some extra space for variables, but it is not significant compared to the space used by the set.

Reasoning Behind Our Approach

Our approach is based on the observation that to determine if all binary codes of size k are present in the given string s, we don't need to generate and check each possible binary code.

Instead, we can use a sliding window technique to efficiently count unique binary codes of size k within the string.

We maintain a set, code_set, to store the unique binary codes we encounter as we slide through the string s.

By ensuring that we only add unique codes to the set, we can efficiently count the unique binary codes of size k.

If the number of unique binary codes in code_set is equal to 2^k, we can conclude that all binary codes of size k are present in the string s.

This approach significantly reduces the time complexity compared to a brute force approach, where we would generate and check every possible binary code.

Our approach's time complexity is O(n * k), where n is the length of the input string, and k is the binary code size we are looking for.

This is an efficient solution for solving the problem.

Related Interview Questions By Company:

• Pacific Atlantic Water Flow LeetCode
• Binary Tree Level Order Traversal LeetCode
• Insertion Sort List LeetCode

Related Interview Questions By Difficulty:

• Length Of Last Word LeetCode
• Repeated Dna Sequences LeetCode
• Isomorphic Strings LeetCode

Related Interview Questions By Category:

• N Queens II LeetCode
• Two City Scheduling LeetCode
• Swap Nodes In Pairs LeetCode

Conclusion

In this blog post, we tackled the LeetCode problem Check If A String Contains All Binary Codes Of Size K (Problem 1461).

We provided a Python solution that efficiently determines whether all binary codes of a given size k exist in a binary string s.

We discussed the problem, provided a step-by-step explanation of the efficient solution, and analyzed its time and space complexity.

We hope this guide has been helpful in understanding the problem and its solution.

If you have any questions, comments, or

suggestions, please feel free to share them.

Your feedback is valuable in helping us improve our content.

If you found this blog post useful, please consider liking, subscribing, and sharing it with others who might benefit from it.

Additionally, if you'd like to support our our platform further, check out our Patreon.

Thank you for joining us in this coding session, and we look forward to seeing you in future discussions and problem-solving adventures.

Question Link: Check if a String Contains all Binary Codes of Size K – LeetCode

Now, it's your turn!

Feel free to comment, ask questions, make suggestions, and share this content with others.

Happy coding!