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
s
using 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
.
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 populatess
with every unique substring of lengthk
present in the strings
. This is done by iterating over the string with a moving window of sizek
. For each positioni
from 0 to(len(s) - k)
, a substring of lengthk
is extracted and added to the set.ss = {s[i : i + k] for i in range(len(s) - k + 1)}
The
range
used for iteration goes up tolen(s) - k + 1
because when extracting a substring of lengthk
starting at positioni
, the last valid position ofi
is wheni + k
equalslen(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 number1
to the leftk
times in binary, which is equivalent to multiplying the number1
by2
exactlyk
times. The result is2^k
, which represents the total number of unique binary strings of lengthk
.return len(ss) == 1 << k
In 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, thens
contains 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.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample 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
ss
to store unique substrings of lengthk
froms
. 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:
ss = {"001", "011", "110"}
Now,
ss
contains 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
. Sincek
is 3, there are2^3
or 8 possible binary numbers (000
,001
,010
,011
,100
,101
,110
,111
).By performing the bitwise shift operation
1 << k
:return len(ss) == 1 << 3 # Evaluates to 3 == 8
In this case, the condition is
false
becauselen(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)
10
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
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
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
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.
Which of the following array represent a max heap?
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
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
Want a Structured Path to Master System Design Too? Donāt Miss This!