1461. Check If a String Contains All Binary Codes of Size K
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:
- Generating all possible k-length substrings from
susing a set comprehension. - Checking if the number of unique substrings (
len(ss)) equals2^k(expressed in Python as1 << k, which is a bit shift operation equivalent to raising 2 to the power ofk).
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.
Which of these properties could exist for a graph but not a tree?
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:
-
Set comprehension: The solution begins by creating a set named
ss. Set comprehension is used to populatesswith every unique substring of lengthkpresent in the strings. This is done by iterating over the string with a moving window of sizek. For each positionifrom 0 to(len(s) - k), a substring of lengthkis extracted and added to the set.1ss = {s[i : i + k] for i in range(len(s) - k + 1)}The
rangeused for iteration goes up tolen(s) - k + 1because when extracting a substring of lengthkstarting at positioni, the last valid position ofiis wheni + kequalslen(s), meaning the substring ends at the last character ofs. -
Bitwise Shift: To determine the total number of unique binary numbers of length
k, the solution uses the bitwise left shift operation1 << k. This operation shifts the number1to the leftktimes in binary, which is equivalent to multiplying the number1by2exactlyktimes. The result is2^k, which represents the total number of unique binary strings of lengthk.1return len(ss) == 1 << kIn this step, the solution compares the size of the set
ss(the number of unique k-length substrings ins) with2^k. If the sizes match, thenscontains every possible binary code of lengthk, and the method returnstrue. Otherwise, it returnsfalse.
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.
Consider the classic dynamic programming of fibonacci numbers, what is the recurrence relation?
Example Walkthrough
To illustrate the solution approach, let's consider a small example with the string s = "00110" and k = 3.
-
Set comprehension: We create a set
ssto store unique substrings of lengthkfroms. 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,
sscontains all k-length substrings that appear ins. In this case, we have exactly 3 different substrings. -
Bitwise Shift: Now we need to check if we have all possible binary numbers of length
k. Sincekis 3, there are2^3or 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 == 8In this case, the condition is
falsebecauselen(ss)is 3 but we need it to be 8 to cover all possible binary numbers of length 3. Therefore, the output would befalse.
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.
Solution Implementation
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)
101class 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}
491class 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};
351function 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}
35Which one best describes the time complexity of the following code?
1int factorial(int n) {
2 if (n < 0) {
3 return -1;
4 } else if (n == 0) {
5 return 1;
6 } else {
7 return n * factorial(n - 1);
8 }
9}
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 using problem constraints.
Depth first search can be used to find whether two components in a graph are connected.
Recommended Readings
Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
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.