1016. Binary String With Substrings Representing 1 To N
Problem Description
The problem requires us to determine if a given binary string s
contains all the binary representations of numbers from 1 to a given positive integer n
as substrings. A substring is a sequence of characters that occur in order without any interruptions within a string. For example, if s = "0110"
and n = 3
, we need to check if the binary representations of 1
("1"
), 2
("10"
), and 3
("11"
) are all present as substrings in s
.
To solve the problem, we need to generate the binary representation of each number from 1 to n
and verify if each representation is a substring of s
.
Intuition
The solution involves a few key observations and steps:
-
Binary Length: The binary representation of a number grows in length when the number doubles. Therefore, as we approach
n
, more significant numbers would have longer binary strings, and if they are not found ins
, we can determine the answer isfalse
without checking smaller numbers. -
Efficient Checking: We start checking from
n
and go down ton//2
. The reasoning is that every binary string that would represent a number from1
ton//2
will also be a substring of a string representing a number fromn//2
ton
. For example, "10" for2
is contained within "110" for6
. -
Performance Boundaries: Since the binary length grows with the number size, the code includes a quick exit condition when
n
is greater than 1000, possibly to avoid performance issues with extremely large strings. However, this condition seems arbitrary and depends on constraints not mentioned in the problem description. It may not be necessary if the input strings
is always large enough to potentially contain all representations. -
All-encompassing Check: To verify if all binary representations are in
s
, a Python built-in functionall()
is used, which checks for the truthiness of all elements in an iterable. In this case, a generator expression checks if each binary representation as a string is a substring ofs
(bin(i)[2:] in s
).
The intuition behind this approach is that by checking the larger half of the range first using string containment operations, one can determine if the binary representations of numbers in the range [1, n]
are substrings of the given string s
with higher efficiency than checking every single number starting from 1.
Solution Approach
The solution approach utilizes a simple and direct method for checking the presence of binary substrings within the given string s
. Below are the components and steps of the implementation using the provided Python code:
-
Function Signature:
def queryString(self, s: str, n: int) -> bool
: This is the function signature wheres
is the input string andn
is the integer until which we need to check the binary representations. The function returns a Boolean value.
-
Early Return Condition:
if n > 1000: return False
: The code immediately returnsFalse
ifn
is more than 1000, implying a performance optimization for large numbers, but as mentioned earlier, this condition may be arbitrary.
-
Main Checking Loop:
return all(bin(i)[2:] in s for i in range(n, n // 2, -1))
: Here the algorithm employs Python's built-in functionall()
which tests if all elements in an iterable are true. The iterable, in this case, is a generator expression that goes through the range of integers fromn
ton // 2
(integer division by 2) in descending order.
-
Binary Conversion and Substring Check:
bin(i)[2:] in s
: For eachi
in the specified range, the built-inbin()
function generates its binary representation as a string and strips off the '0b' prefix with[2:]
. Then we check whether this binary representation is a substring ofs
.
-
Data Structures:
- No additional data structures are used in this solution. The input string
s
and integern
are directly utilized within the algorithm.
- No additional data structures are used in this solution. The input string
-
Algorithmic Patterns:
- The algorithm does not use complex patterns or advanced data structures. It relies on Python’s expressive syntax and built-in functions to perform substring checking efficiently.
The loop iterates through only half of the specified range (from n
to n // 2
) in reverse order because if i
can be represented within s
as a binary string, all smaller numbers can also be substrings of those representations or will have occurred earlier within the binary sequence. This approach takes advantage of the fact that binary representations of numbers are nested within those of larger numbers, providing a significant performance improvement over checking every single number individually from 1 to n
.
In summary, the code leverages Python's capabilities to check for the presence of each binary representation of numbers in the given range within the string s
succinctly and efficiently.
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, let's consider an example where s = "01101101"
and n = 4
. We would like to determine if the binary representations of numbers from 1 to 4, which are "1" (1), "10" (2), "11" (3), and "100" (4), appear as substrings in s
.
Steps:
-
Check for Early Return: The first check in our solution is to see if
n
is greater than 1000. In this case,n = 4
, so we do not return early and proceed. -
Initialize the Main Loop: Starting with
i = 4
and iterating down toi = 2
(half ofn
), we check each binary representation to see if it's a substring ins
. -
Binary Conversion:
- For
i = 4
, we convert4
to binary, getting"100"
. Check if"100"
is ins
. It is not, so we could already returnFalse
. However, continue for illustration purposes. - For
i = 3
, convert3
to binary, yielding"11"
. Check if"11"
is a substring ofs
, which it is, ass
is"01101101"
. - For
i = 2
, convert2
to binary to get"10"
. We then check if"10"
is part ofs
, and indeed, it is present.
- For
-
Evaluate with
all()
Function: Use theall()
function to verify whether all these checks (i = 4
toi = 2
) areTrue
. Since"100"
was not found,all()
will returnFalse
. -
No Additional Data Structures: We have not used additional data structures outside the string
s
and the numbers we're checking. -
Conclusion: Since not all binary representations from 1 to 4 were found as substrings in
s
("100"
was missing), theall()
function will evaluate toFalse
. Therefore, the given strings
does not contain all binary representations as substrings.
This step-by-step walkthrough demonstrates the simplicity and efficiency of the approach by focusing on checking only the necessary binary representations and utilizing Python's built-in tools.
Solution Implementation
1class Solution:
2 def query_string(self, string: str, upper_bound: int) -> bool:
3 # If the upper bound (n) is greater than 1000, return false as per the given logic.
4 if upper_bound > 1000:
5 return False
6
7 # 'all' checks whether all elements in the iterable are True.
8 # The loop starts from 'upper_bound' and goes till 'upper_bound // 2' (integer division by 2), moving backwards.
9 # 'bin(i)[2:]' converts the integer 'i' to its binary representation in string format, stripping off the '0b' prefix.
10 # 'in string' checks if each binary representation is a substring of the input string 'string'.
11 return all(bin(i)[2:] in string for i in range(upper_bound, upper_bound // 2, -1))
12
13# Example usage:
14# sol = Solution()
15# result = sol.query_string("0110", 3)
16# print(result) # This would print 'True' if all binary numbers from n to n//2 are substrings of "0110"
17
1class Solution {
2
3 /**
4 * Checks if all binary representations of numbers from 1 to n are substrings of the string s.
5 *
6 * @param s The string in which binary representations are to be searched.
7 * @param n The maximum value up to which binary representations should be checked.
8 * @return True if all binary representations from 1 to n are found in s, otherwise False.
9 */
10 public boolean queryString(String s, int n) {
11 // If n is greater than the maximum allowed value (as binary representation within the string),
12 // which is 2^10 - 1 = 1023 for a 10-bit binary number, return false as the condition can't be met.
13 if (n > 1023) {
14 return false;
15 }
16 // Iterate from n down to n / 2 since every number smaller than n/2 is a binary substring of a number
17 // that is larger than n/2 (because the binary representation of a number is also a suffix of the
18 // binary representation of its double).
19 // If a substring representing the binary of i is not found within string s, return false.
20 for (int i = n; i > n / 2; i--) {
21 if (!s.contains(Integer.toBinaryString(i))) {
22 return false;
23 }
24 }
25 // Return true if all required binary substrings have been found.
26 return true;
27 }
28}
29
1#include <bitset>
2#include <string>
3
4class Solution {
5public:
6 // Function to check if all binary representations of numbers
7 // from 1 to n are substrings of the input string s.
8 bool queryString(std::string s, int n) {
9 // Early exit condition if n is greater than the maximum
10 // value representable with 10 binary digits.
11 if (n > 1023) {
12 return false;
13 }
14 // Loop through numbers starting from n to half of n
15 // since the bit representation of numbers less than n/2
16 // will always be contained in the bit representation of
17 // numbers between n/2 and n.
18 for (int i = n; i > n / 2; --i) {
19 // Convert the number to binary (bitset) and then to string.
20 std::string binaryString = std::bitset<32>(i).to_string();
21 // Remove leading zeroes from the binary string.
22 binaryString.erase(0, binaryString.find_first_not_of('0'));
23 // Check if the resulting binary string is a substring of s.
24 if (s.find(binaryString) == std::string::npos) {
25 // If not found, return false immediately.
26 return false;
27 }
28 }
29 // All required binary representations are substrings of s. Return true.
30 return true;
31 }
32};
33
1/**
2 * Checks if a binary string represents all numbers from 1 to n.
3 *
4 * @param {string} binaryString - The string consisting of binary digits.
5 * @param {number} maxNumber - The maximum number to check up to (inclusive).
6 * @returns {boolean} - Returns true if all numbers from 1 to maxNumber are
7 * represented in the binaryString, otherwise false.
8 */
9function queryString(binaryString: string, maxNumber: number): boolean {
10 // Check if the maxNumber is larger than the largest number that can be represented
11 // with a 10-bit binary number, which is 1023.
12 if (maxNumber > 1023) {
13 return false;
14 }
15 // Iterate from the maxNumber down to half of it, since every number from 1 to n / 2
16 // will be a substring of the binary representation of numbers from n / 2 + 1 to n.
17 for (let currentNum = maxNumber; currentNum > maxNumber / 2; --currentNum) {
18 // Convert the current number to its binary string representation.
19 const binaryRepresentation = currentNum.toString(2);
20 // Check if the current binary representation is a substring of binaryString.
21 // If it is not found, the method returns -1, therefore, return false.
22 if (binaryString.indexOf(binaryRepresentation) === -1) {
23 return false;
24 }
25 }
26 // If all necessary binary representations are found in the string, return true.
27 return true;
28}
29
Time and Space Complexity
The time complexity of the provided code can be determined by analyzing the two main operations: the all
function and the string containment check in
.
Time Complexity:
- The
all
function iterates over the range fromn
ton // 2
, decreasing by 1 each time. This results in approximatelyn/2
iterations. - For each iteration, the string containment check
in
is performed, which, in the worst case, has a complexity ofO(m)
, wherem
is the length of the strings
.
Therefore, the overall worst-case time complexity is O(m * n/2)
, as the containment check is performed n/2
times.
Space Complexity:
- No extra space is used for data storage that scales with the input size; only a fixed number of variables are used.
- The binary representation string created for each number
i
is temporary and its length is at mostO(log(n))
.
Hence, the space complexity is O(1)
, which means it is constant since the space required does not grow with the input size n
or the string length m
.
Learn more about how to find time and space complexity quickly using problem constraints.
Which algorithm should you use to find a node that is close to the root of the tree?
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
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.