Problem statement

https://leetcode.com/problems/binary-string-with-substrings-representing-1-to-n/

Solution

First of all if n is big, then we have at least n//3 substrings of the same length and if n > len(s) * 3, we do not have enough substrings of the same length. In the opposite case we can check bruteforce: complexity will be O(n^2).

Complexity

It is O(n^2) for time and O(n) for space.

Code

class Solution:
    def queryString(self, s, n):
        if n > len(s) * 3: return False
        return all(bin(i + 1)[2:] in s for i in range(n))

Solution 2

We can check all substrings of length <= log(n).

Complexity

Time complexity is O(s log^2n).

Code

class Solution:
    def queryString(self, s, n):
        ans = set()
        for i in range(len(s)):
            for ii in range(i, i + n.bit_length()): 
                x = int(s[i:ii+1], 2)
                if 1 <= x <= n: ans.add(x)
        return len(ans) == n

Remark

We can also put all these substrings in trie and get O(s log n) solution. Or we can check range (N//2, N] only and check substrings of length log(n) and log(n) - 1.