# LeetCode 1016: Binary String With Substrings Representing 1 To N

## Problem Restatement

We are given a binary string `s` and a positive integer `n`.

We need to return `true` if every integer from `1` to `n` can be represented as a substring of `s` when the substring is interpreted as a binary number.

The official constraints state that `1 <= s.length <= 1000` and `1 <= n <= 10^9`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Binary string `s` and integer `n` |
| Output | `true` if all integers `1` to `n` have their binary representation as a substring of `s` |

Function shape:

```python
def queryString(s: str, n: int) -> bool:
    ...
```

## Examples

Example 1:

```python
s = "0110"
n = 3
```

- `1` in binary: `"1"` → in `"0110"` ✓
- `2` in binary: `"10"` → in `"0110"` ✓
- `3` in binary: `"11"` → in `"0110"` ✓

Answer:

```python
True
```

Example 2:

```python
s = "0110"
n = 4
```

- `4` in binary: `"100"` → not in `"0110"` ✗

Answer:

```python
False
```

## Key Insight

If `n` is large enough, this becomes impossible even with a long `s`. Specifically, a binary string of length `L` has at most `L * (L + 1) / 2` distinct substrings. For all integers `1` to `n` to be represented, each must correspond to a unique substring. So we only need to check integers down to a practical limit.

For a string `s` of length `1000`, all distinct substrings of length `>= 20` are fewer than `1000 * 20 = 20000`. Since `2^20 > 10^6`, for `n > 2 * len(s)`, the answer is `False`.

So for `n > 2 * len(s)`, return `False`. Otherwise, check each integer from `n` down to `1`.

## Algorithm

1. If `n > 2 * len(s)`, return `False`.
2. For each integer `i` from `1` to `n`:
   - Convert `i` to binary string (without the `0b` prefix).
   - Check if this binary string is a substring of `s`.
   - If not, return `False`.
3. Return `True`.

## Correctness

For large `n`, the number of integers to check exceeds the number of substrings `s` can contain, so the answer must be `False`.

For small `n`, we directly check each integer.

## Edge Cases

- Check the smallest and largest valid search values; off-by-one errors usually appear at the boundaries.
- Decide whether the predicate is looking for the first true value, the last true value, or an exact match.
- When the target is absent, the loop should still terminate and return the problem-specific failure value.

## Complexity

Let `L = len(s)`.

| Metric | Value | Why |
|---|---:|---|
| Time | `O(L^2)` | At most `O(L)` integers checked, each substring search is `O(L)` |
| Space | `O(L)` | Binary representations |

## Common Pitfalls

- Do not mix inclusive and half-open bounds inside the same loop.
- Make sure each branch strictly reduces the search interval.

## Implementation

```python
class Solution:
    def queryString(self, s: str, n: int) -> bool:
        if n > 2 * len(s):
            return False

        for i in range(1, n + 1):
            if bin(i)[2:] not in s:
                return False

        return True
```

## Code Explanation

Early return for impossible cases:

```python
if n > 2 * len(s):
    return False
```

Check each integer's binary representation:

```python
for i in range(1, n + 1):
    if bin(i)[2:] not in s:
        return False
```

`bin(i)[2:]` gives the binary representation without the `"0b"` prefix.

The `in` operator checks for substring containment in `O(L)` time.

## Testing

```python
def run_tests():
    s = Solution()

    assert s.queryString("0110", 3) == True
    assert s.queryString("0110", 4) == False
    assert s.queryString("1", 1) == True
    assert s.queryString("0", 1) == False
    assert s.queryString("1111110", 5) == False

    print("all tests passed")

run_tests()
```

| Test | Expected | Why |
|---|---:|---|
| `"0110"`, `3` | `True` | All `1-3` are substrings |
| `"0110"`, `4` | `False` | `"100"` not in `"0110"` |
| `"1"`, `1` | `True` | `"1"` is in the string |
| `"0"`, `1` | `False` | `"1"` is not in the string |
| `"1111110"`, `5` | `False` | `"101"` not in the string |