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 <= 1000N <= 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;
}
}

This site uses Akismet to reduce spam. Learn how your comment data is processed.