# 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 <= S.length <= 1000`

`1 <= N <= 10^9`

#### Thoughts:

Time Complexity

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

- 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 0b11111010000The 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)`

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

## 0 Comments