1023. Binary String With Substrings Representing 1 To N

Given a binary string `S` (a string consisting only of ‘0’ and ‘1’s) and a positive integer `N`, return true if and only if for every integer X from 1 to N, the binary representation of X is a substring of S.

Example 1:

Input:

```S = "0110", N = 3
```

Output:

```true
```

Example 2:

Input:

```S = "0110", N = 4
```

Output:

```false
```

Note:

1. `1 <= S.length <= 1000`
2. `1 <= N <= 10^9`

Thoughts:

I was thinking there could be an amazing algo to deal with it.
Well, the solution is quite straight forward, just follow your mind. I didn’t even give it a try during the contest.
It’s kind of unexpected for a median level question.
For the time complexity, here’s a great analysis from lee215:
Time Complexity
1. Prove I, check number of substring

Pick two indices, there are at most `S^2` substrings,
so `S` can contains at most `S^2` integers
Time complexity upper bound `O(S^2)`

1. Prove II, Check the continuous digits
Meanwhile I know the interviewer and my reader won’t be satisfied,
as they want no more “cheat”.

Here I have a brief demonstration to give the time complexity an acceptable upper bound.

Have a look at the number 1001 ~ 2000 and their values in binary.

1001 0b1111101001
1002 0b1111101010
1003 0b1111101011

1997 0b11111001101
1998 0b11111001110
1999 0b11111001111
2000 0b11111010000

The number 1001 ~ 2000 have 1000 different continuous 10 digits.
The string of length `S` has at most `S - 9` different continuous 10 digits.
So `S <= 1000``N <= 2000`.

So `S * 2` is a upper bound for `N`.
If `N > S * 2`, we can return `false` directly.

It’s the same to prove with the numbers 512 ~ 1511, or even smaller range.

Time complexity upper bound `O(S)`

And finally, the code:
```class Solution {

/**
* @param String \$S
* @param Integer \$N
* @return Boolean
*/
function queryString(\$S, \$N) {
while(\$N > 1){
\$binary = decbin(\$N);
if(strpos(\$S, \$binary) === false){
return false;
}
\$N --;
}
return true;
}
}```