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

MediumBit ManipulationHash TableStringHash FunctionRolling Hash
Leetcode Link

Problem Description

In this problem, we are given a binary string s which is comprised of only '0's and '1's. We are also given an integer k. The task is to determine whether or not every possible binary number of length k could be found as a substring within the binary string s. A substring is any consecutive sequence of characters within a string. If all possible binary numbers of length k are present, we should return true. If at least one such binary number is missing, we should return false.

For example, if s = "0110" and k = 2, the binary codes of length 2 are '00', '01', '10', and '11'. In the given string '01' and '10' are present but '00' and '11' are not, so the function should return false.

The problem challenges us to examine segments within the string and to account for every possible combination without missing any, ensuring the string s could represent all possible binary numbers of the given length k.

Intuition

To solve this problem, the intuition is to generate all possible substrings of length k from the given string s and store them in a set to avoid duplicates. A set is chosen because it automatically handles duplicates and allows us to count unique substrings efficiently.

The next step is to compare the number of unique substrings obtained with the total number of possible combinations for a binary number of length k. Since there are two possible values (0 or 1) for each position, the total number of unique k-length binary numbers is 2^k.

The Python code accomplishes this by:

  1. Generating all possible k-length substrings from s using a set comprehension.
  2. Checking if the number of unique substrings (len(ss)) equals 2^k (expressed in Python as 1 << k, which is a bit shift operation equivalent to raising 2 to the power of k).

If these two numbers match, all binary codes of length k are present in the string s, and the function returns true. Otherwise, at least one code is missing, so it returns false.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece:

Which of the following array represent a max heap?

Solution Approach

The solution to this problem uses set comprehension and bitwise operations as its main algorithmic tools. Let's walk through the implementation step by step:

  1. Set comprehension: The solution begins by creating a set named ss. Set comprehension is used to populate ss with every unique substring of length k present in the string s. This is done by iterating over the string with a moving window of size k. For each position i from 0 to (len(s) - k), a substring of length k is extracted and added to the set.

    1ss = {s[i : i + k] for i in range(len(s) - k + 1)}

    The range used for iteration goes up to len(s) - k + 1 because when extracting a substring of length k starting at position i, the last valid position of i is when i + k equals len(s), meaning the substring ends at the last character of s.

  2. Bitwise Shift: To determine the total number of unique binary numbers of length k, the solution uses the bitwise left shift operation 1 << k. This operation shifts the number 1 to the left k times in binary, which is equivalent to multiplying the number 1 by 2 exactly k times. The result is 2^k, which represents the total number of unique binary strings of length k.

    1return len(ss) == 1 << k

    In this step, the solution compares the size of the set ss (the number of unique k-length substrings in s) with 2^k. If the sizes match, then s contains every possible binary code of length k, and the method returns true. Otherwise, it returns false.

The data structure used (set) is essential for efficiently managing unique values and the operation (bitwise shift) simplifies the calculation of total combinations without having to invoke heavier mathematical operations.

This approach is both space-efficient, since only unique substrings are kept, and time-efficient, as it avoids unnecessary calculations by leveraging the properties of binary numbers and bitwise operations.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Depth first search can be used to find whether two components in a graph are connected.

Example Walkthrough

To illustrate the solution approach, let's consider a small example with the string s = "00110" and k = 3.

  1. Set comprehension: We create a set ss to store unique substrings of length k from s. Here's how we do it:

    • Start at the beginning of the string: The first k-length substring is "001".
    • Move to the next character: The next substring is "011".
    • Continue this process until the end of the string: We then get "110".

    The set comprehension in the code is executed like this:

    1ss = {"001", "011", "110"}

    Now, ss contains all k-length substrings that appear in s. In this case, we have exactly 3 different substrings.

  2. Bitwise Shift: Now we need to check if we have all possible binary numbers of length k. Since k is 3, there are 2^3 or 8 possible binary numbers (000, 001, 010, 011, 100, 101, 110, 111).

    By performing the bitwise shift operation 1 << k:

    1return len(ss) == 1 << 3  # Evaluates to 3 == 8

    In this case, the condition is false because len(ss) is 3 but we need it to be 8 to cover all possible binary numbers of length 3. Therefore, the output would be false.

Using this approach, the algorithm efficiently determines whether the binary string s contains every possible binary number as a substring of length k. In this example, some binary numbers like '000', '010', '100', '101', and '111' are missing from s, so not all binary numbers of length k are represented in it.

Not Sure What to Study? Take the 2-min Quiz:

Which data structure is used to implement priority queue?

Python Solution

1class Solution:
2    def hasAllCodes(self, s: str, k: int) -> bool:
3        # Create a set to store all unique substrings of length k
4        unique_substrings = {s[i: i + k] for i in range(len(s) - k + 1)}
5      
6        # Check if the number of unique substrings of length k
7        # is equal to 2^k (which is the total number of possible
8        # binary strings of length k)
9        return len(unique_substrings) == (1 << k)
10

Java Solution

1class Solution {
2
3    public boolean hasAllCodes(String s, int k) {
4        // Calculate the length of the string.
5        int stringLength = s.length();
6      
7        // If there are not enough substrings to cover all possible 
8        // binary numbers of length k, return false.
9        if (stringLength - k + 1 < (1 << k)) {
10            return false;
11        }
12      
13        // Create an array to keep track of which binary numbers
14        // of length k we have seen.
15        boolean[] visited = new boolean[1 << k];
16      
17        // Convert the first 'k' bits of the string to a numerical value.
18        int currentValue = Integer.parseInt(s.substring(0, k), 2);
19        visited[currentValue] = true;
20      
21        // Iterate over the string to check all possible substrings
22        // of length k.
23        for (int i = k; i < stringLength; ++i) {
24            // Calculate the bit to remove from the front of the
25            // current sliding window of size k.
26            int frontBit = (s.charAt(i - k) - '0') << (k - 1);
27          
28            // Calculate the bit to add to the back of the current
29            // sliding window of size k.
30            int backBit = s.charAt(i) - '0';
31          
32            // Update the current sliding window value.
33            currentValue = (currentValue - frontBit) << 1 | backBit;
34          
35            // Mark this new value as seen.
36            visited[currentValue] = true;
37        }
38      
39        // If any binary number of length k hasn't been visited,
40        // return false, otherwise return true.
41        for (boolean hasVisited : visited) {
42            if (!hasVisited) {
43                return false;
44            }
45        }
46        return true;
47    }
48}
49

C++ Solution

1class Solution {
2public:
3    bool hasAllCodes(string str, int k) {
4        int strSize = str.size(); // Size of input string
5      
6        // Check if there is enough length in the string to have all k-bit codes
7        if (strSize - k + 1 < (1 << k)) return false;
8      
9        // Initialize a boolean vector to track which k-bit patterns have been visited
10        vector<bool> visited(1 << k, false);
11      
12        // Convert the first k bits of the string to a number and mark as visited
13        int currentNumber = stoi(str.substr(0, k), nullptr, 2);
14        visited[currentNumber] = true;
15      
16        // Traverse the rest of the string to find all distinct k-bit codes
17        for (int i = k; i < strSize; ++i) {
18            // Remove the leading bit and leave space at the end
19            int leadingBit = (str[i - k] - '0') << (k - 1);
20            // Extract the last bit of the current sliding window
21            int lastBit = str[i] - '0';
22            // Update currentNumber by removing the leading bit and adding the new trailing bit
23            currentNumber = (currentNumber - leadingBit) << 1 | lastBit;
24            // Mark the new k-bit number as visited
25            visited[currentNumber] = true;
26        }
27      
28        // Check if there is any k-bit code that has not been visited
29        for (bool isVisited : visited) {
30            if (!isVisited) return false; // Return false if any code is not found
31        }
32        return true; // All k-bit codes are found, return true
33    }
34};
35

Typescript Solution

1function hasAllCodes(str: string, k: number): boolean {
2    let strSize: number = str.length; // Size of input string
3  
4    // Check if there is enough length in the string to have all k-bit codes
5    if (strSize - k + 1 < (1 << k)) return false;
6  
7    // Initialize an array to track which k-bit patterns have been visited
8    let visited: boolean[] = new Array(1 << k).fill(false);
9  
10    // Helper function to convert a binary string to a number
11    const binToNum = (bin: string): number => parseInt(bin, 2);
12
13    // Convert the first k bits of the string to a number and mark as visited
14    let currentNumber: number = binToNum(str.substring(0, k));
15    visited[currentNumber] = true;
16  
17    // Traverse the rest of the string to find all distinct k-bit codes
18    for (let i: number = k; i < strSize; ++i) {
19        // Remove the leading bit and leave space at the end
20        let leadingBit: number = (parseInt(str[i - k]) << (k - 1));
21        // Extract the last bit of the current sliding window
22        let lastBit: number = parseInt(str[i]);
23        // Update currentNumber by removing the leading bit and adding the new trailing bit
24        currentNumber = ((currentNumber - leadingBit) << 1) | lastBit;
25        // Mark the new k-bit number as visited
26        visited[currentNumber] = true;
27    }
28  
29    // Check if there is any k-bit code that has not been visited
30    for (let isVisited of visited) {
31        if (!isVisited) return false; // Return false if any code is not found
32    }
33    return true; // All k-bit codes are found, return true
34}
35
Fast Track Your Learning with Our Quick Skills Quiz:

A heap is a ...?

Time and Space Complexity

Time Complexity

The time complexity of the given code primarily comes from the set comprehension used to create a set ss of all substrings of length k from the string s. The comprehension iterates over each index of the string from 0 to len(s) - k inclusively, which results in len(s) - k + 1 iterations. For each iteration, a substring of length k is created, which has its own time complexity of O(k). Thus, the overall time complexity of this part is O(k * (len(s) - k + 1)).

Additionally, the operation 1 << k performs a bitwise left shift which has a time complexity of O(1) since it is an operation over a fixed-size integer (which is independent of the input size).

Therefore, the total time complexity of the function hasAllCodes is O(k * (len(s) - k + 1)).

Space Complexity

The space complexity is driven by the space required to store all unique substrings of length k from the string s. The maximum number of unique substrings that can be stored in set ss is 2^k, since each k-length substring is a possible combination of k bits, and there are 2^k possible combinations of k bits.

However, the number of substrings that can actually be stored is limited by the number of substrings that we can generate from s, which is len(s) - k + 1. Therefore, the space complexity of the set ss is O(min(2^k, len(s) - k + 1)).

Considering both possible limits, the overall space complexity of the function hasAllCodes is O(min(2^k, len(s) - k + 1)).

Learn more about how to find time and space complexity quickly.


Recommended Readings


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫