# Binary String With Substrings Representing 1 To N
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/binary-string-with-substrings-representing-1-to-n)
Canonical: https://scaleengineer.com/dsa/problems/binary-string-with-substrings-representing-1-to-n
**Patterns:** [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation)
**Data structures:** Hash Table, String
---
## Problem
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:** true

**Example 2:**

**Input:** s = "0110", n = 4
**Output:** false

**Constraints:**

* `1 <= s.length <= 1000`
* `s[i]` is either `'0'` or `'1'`.
* `1 <= n <= 109`

# Approaches
## Brute-Force Iteration
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.
**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`.
**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.
### Explanation
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.

```java
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;
    }
}
```
### Algorithm
1.  Iterate through each integer `i` from 1 to `n`.
2.  For each integer `i`, convert it to its binary string representation. For example, if `i` is 3, its binary string is `"11"`.
3.  Check if this binary string is a substring of the input string `s`.
4.  If, for any `i`, its binary representation is not found in `s`, we can immediately return `false`.
5.  If the loop completes without finding any missing binary representations, it means all integers from 1 to `n` are represented. Return `true`.

## Bounded Iteration
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`.
**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)`.
**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.
### Explanation
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.

```java
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;
    }
}
```
### Algorithm
1.  Iterate through each integer `i` from `n` down to 1.
2.  Convert `i` to its binary string representation, `b`.
3.  Check if `b` is a substring of `s`.
4.  If `b` is not found, return `false`.
5.  If the loop completes, return `true`.

## Efficient Substring Generation
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.
**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`).
**Pros:** Highly efficient, with a time complexity that depends on the length of `s`, not `n`.; 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.
### Explanation
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`.

```java
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;
    }
}
```
### Algorithm
1.  Create a `HashSet` to store the unique integers we find.
2.  Iterate through the string `s` with an outer loop, using `i` as the starting index of a substring.
3.  For each `i`, start an inner loop with index `j` from `i` to the end of the string.
4.  In the inner loop, progressively build the integer value represented by the substring `s[i...j]`.
5.  To avoid dealing with numbers larger than `n` or overflowing standard integer types, we can use a `long` for the current number and break the inner loop if the number exceeds `n`.
6.  If the parsed number is between 1 and `n` (inclusive), add it to our `HashSet`.
7.  After iterating through all relevant substrings, check if the size of the `HashSet` is equal to `n`. If it is, we have found all numbers from 1 to `n`.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
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;
  }
};

```

### Python

```python
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))

```