LeetCode 1461: Check If a String Contains All Binary Codes of Size K Solution

Master LeetCode problem 1461 (Check If a String Contains All Binary Codes of Size K), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1461. Check If a String Contains All Binary Codes of Size K

Medium

Hash Table String Bit Manipulation Rolling Hash Hash Function

Problem Explanation

Explanation:

To solve this problem, we can iterate through all possible binary codes of size k and check if each one is a substring of the given binary string s. We can achieve this by maintaining a HashSet to store all unique substrings of size k that we encounter while iterating through the string s. Finally, we check if the size of the HashSet is equal to 2^k, which indicates that all possible binary codes of size k have been found in the string s.

Algorithm:
1. Initialize a HashSet to store unique substrings of size k.
2. Iterate through the binary string s with a sliding window of size k and add each substring of size k to the HashSet.
3. Check if the size of the HashSet is equal to 2^k.
4. Return true if all binary codes of size k are found, otherwise return false.
Time Complexity: O(n * k), where n is the length of the binary string s.
Space Complexity: O(2^k), to store unique substrings of size k. :

Solution Code

import java.util.HashSet;

class Solution {
    public boolean hasAllCodes(String s, int k) {
        HashSet<String> set = new HashSet<>();
        for (int i = 0; i <= s.length() - k; i++) {
            set.add(s.substring(i, i + k));
        }
        return set.size() == Math.pow(2, k);
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1461 (Check If a String Contains All Binary Codes of Size K)?

This page provides optimized solutions for LeetCode problem 1461 (Check If a String Contains All Binary Codes of Size K) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1461 (Check If a String Contains All Binary Codes of Size K)?

The time complexity for LeetCode 1461 (Check If a String Contains All Binary Codes of Size K) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1461 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1461 in Java, C++, or Python.

Back to LeetCode Solutions