Binary String With Substrings Representing 1 To N
MedPrompt
Given a binary string s and a positive integer n, return true if the binary representation of all the integers in the range [1, n] are substrings of s, or false otherwise.
A substring is a contiguous sequence of characters within a string.
Example 1:
Input: s = "0110", n = 3
Output: trueExample 2:
Input: s = "0110", n = 4
Output: false
Constraints:
1 <= s.length <= 1000s[i]is either'0'or'1'.1 <= n <= 109
Approaches
3 approaches with complexity analysis and trade-offs.
The most straightforward way to solve this problem is to follow the problem statement directly. We can iterate through every number from 1 to n, convert each number to its binary form, and then check if that binary string exists within s. If we find even one number whose binary representation is not a substring of s, we know the condition is not met and can stop early. If we successfully check all numbers up to n, the condition is satisfied.
Algorithm
- Iterate through each integer
ifrom 1 ton. - For each integer
i, convert it to its binary string representation. For example, ifiis 3, its binary string is"11". - Check if this binary string is a substring of the input string
s. - If, for any
i, its binary representation is not found ins, we can immediately returnfalse. - If the loop completes without finding any missing binary representations, it means all integers from 1 to
nare represented. Returntrue.
Walkthrough
This brute-force method involves a simple loop from 1 to n. In each iteration, we take the current number i, generate its binary equivalent using a built-in function like Integer.toBinaryString(i), and then use a string searching method like s.contains() to see if this binary string is present in s. While simple to understand and implement, its performance is poor due to the potentially huge number of iterations (up to n) combined with the cost of string searching in each iteration.
class Solution { public boolean queryString(String s, int n) { for (int i = 1; i <= n; i++) { String binaryString = Integer.toBinaryString(i); if (!s.contains(binaryString)) { return false; } } return true; }}Complexity
Time
O(N * L * log N) Where `N` is the input integer `n`, and `L` is the length of the string `s`. The loop runs `N` times. Inside the loop, converting `i` to binary takes `O(log i)` time, and `s.contains()` takes `O(L * log i)` time in the worst case. This makes the total complexity too high for the given constraints.
Space
O(log n) This is the space required to store the binary string representation of the largest number, `n`.
Trade-offs
Pros
Very easy to understand and implement.
It is a direct translation of the problem statement into code.
Cons
This approach is very slow and will lead to a 'Time Limit Exceeded' error on platforms like LeetCode for larger values of
n.The time complexity is directly proportional to
n, which can be up to 10^9.
This approach uses the same logic as the brute-force method but with a crucial insight based on the problem's constraints. The key observation is that for the answer to be true, n cannot be excessively large compared to the length of s (L). A string of length L can only have a limited number of unique substrings. Using the pigeonhole principle, we can show that if n is larger than a small multiple of L (e.g., 4*L), it's guaranteed that s cannot contain all the required binary strings. For L=1000, n must be less than ~2000. Therefore, a simple loop from n down to 1 is feasible because it will only execute a limited number of times for any test case where the answer could be true.
Algorithm
- Iterate through each integer
ifromndown to 1. - Convert
ito its binary string representation,b. - Check if
bis a substring ofs. - If
bis not found, returnfalse. - If the loop completes, return
true.
Walkthrough
The algorithm is identical in implementation to the brute-force approach, but we typically iterate from n downwards. This might fail slightly faster if a large number is missing. The reason this approach passes is due to a mathematical property of the problem: a string s of length L cannot contain all binary numbers of length k if 2^(k-1) > L - k + 1. For L=1000, this inequality holds for k=11. This implies that if n is large enough to include numbers whose binary representation is 11 bits long (i.e., n >= 1024), there will be a missing number. This effectively puts a small upper bound on the value of n for which the function can return true, making the simple loop fast enough.
class Solution { public boolean queryString(String s, int n) { // The constraints on s.length() imply that n cannot be very large // for the result to be true. For s.length() = 1000, n must be < ~2000. // Thus, this simple loop is efficient enough. for (int i = n; i > 0; i--) { String binaryString = Integer.toBinaryString(i); if (!s.contains(binaryString)) { return false; } } return true; }}Complexity
Time
O(L^2 * log L) In cases where the answer can be `true`, `n` is bounded by `O(L)`. The loop runs `O(L)` times. Inside, `s.contains()` takes `O(L * log L)`. This gives an effective complexity that is polynomial in `L` and independent of the input `n`.
Space
O(log n) The space is dominated by storing the binary string for the current number `i`. Since `n` is effectively bounded by `O(L)`, this is `O(log L)`.
Trade-offs
Pros
Simple implementation.
Passes within time limits due to implicit constraints on
n.
Cons
The reasoning for why this approach is efficient enough is not immediately obvious from the code itself.
The performance still relies on the efficiency of the underlying
String.contains()method.
Instead of iterating from 1 to n, a more efficient approach is to reverse the logic: generate all numbers that can be formed by substrings of s and check if this set of numbers contains all integers from 1 to n. Since n can be up to 10^9, its binary representation will have at most 30 bits. This means we only need to consider substrings of s up to length 30. This significantly limits the number of substrings we need to parse and check.
Algorithm
- Create a
HashSetto store the unique integers we find. - Iterate through the string
swith an outer loop, usingias the starting index of a substring. - For each
i, start an inner loop with indexjfromito the end of the string. - In the inner loop, progressively build the integer value represented by the substring
s[i...j]. - To avoid dealing with numbers larger than
nor overflowing standard integer types, we can use alongfor the current number and break the inner loop if the number exceedsn. - If the parsed number is between 1 and
n(inclusive), add it to ourHashSet. - After iterating through all relevant substrings, check if the size of the
HashSetis equal ton. If it is, we have found all numbers from 1 ton.
Walkthrough
This method avoids iterating up to n. We iterate through s to find all possible numbers it represents. We use a HashSet to keep track of the unique numbers from 1 to n that we've found. We can iterate through all substrings, parse them as binary numbers, and if a number is within the [1, n] range, we add it to our set. A key optimization is to realize that since n < 2^31, any binary string longer than 31 characters will represent a number larger than n. So, for each starting position i, the inner loop for j only needs to run about 31 times at most. After checking all substrings, we simply verify if the number of unique integers found is equal to n.
import java.util.HashSet; class Solution { public boolean queryString(String s, int n) { HashSet<Integer> found = new HashSet<>(); for (int i = 0; i < s.length(); i++) { // We only care about substrings that start with '1' if (s.charAt(i) == '0') { continue; } long num = 0; for (int j = i; j < s.length(); j++) { num = num * 2 + (s.charAt(j) - '0'); if (num > n) { // Optimization: any longer substring will also be > n break; } found.add((int) num); } } return found.size() == n; }}Complexity
Time
O(L * log n) Where `L` is the length of `s`. The outer loop runs `L` times. The inner loop runs at most `log2(n)` times (about 30-31), because once the parsed number `num` exceeds `n`, we break. This makes the approach very fast.
Space
O(L * log n) The `HashSet` can, in the worst case, store one number for each substring of `s` whose value is less than or equal to `n`. The number of such substrings is at most `L * log n` (since the length of substrings is limited by `log n`).
Trade-offs
Pros
Highly efficient, with a time complexity that depends on the length of
s, notn.This is the most robust solution that handles all constraints effectively.
Cons
Slightly more complex to implement compared to the iterative approaches.
Uses more space to store the set of found numbers.
Solutions
Solution
class Solution {public boolean queryString(String s, int n) { if (n > 1023) { return false; } for (int i = n; i > n / 2; i--) { if (!s.contains(Integer.toBinaryString(i))) { return false; } } return true; }}class Solution {public: bool queryString(string s, int n) { if (n > 1023) { return false; } for (int i = n; i > n / 2; --i) { string b = bitset<32>(i).to_string(); b = b.substr(b.find_first_not_of('0')); if (s.find(b) == string ::npos) { return false; } } return true; }};class Solution: def queryString(self, s: str, n: int) -> bool: if n > 1000: return False return all(bin(i)[2:] in s for i in range(n, n // 2, - 1))Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.