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

Difficulty: interview

Starter code:

class Solution:
    def queryString(self, S: str, N: int) -> bool:
        

Solutions:
class Solution:
    def queryString(self, S: str, N: int) -> bool:
        for i in range(1,N+1):
            b = bin(i).replace('0b','')
            if b not in S:
               return False
        return True

class Solution:
    def int_to_bin(self,x):
        ret=''
        if x==0:
            return '0' 
        while x>0:
            ret=str(x%2)+ret 
            x=x//2 
        return ret
    def queryString(self, S: str, N: int) -> bool:
        mp={} 
        max_len=min(31,len(S)) 
        for k in range(1,max_len+1):
            for i in range(len(S)-k+1):
                mp[S[i:i+k]]=True
        for i in range(1,N+1):
            if self.int_to_bin(i) not in mp:
                return False 
        return True


class Solution:
    def queryString(self, S: str, N: int) -> bool:
        for i in range(1,N+1):
            if bin(i)[2:] not in S:
                return False
        
        return True

class Solution:
    def queryString(self, S: str, N: int) -> bool:
        # (bin(1))
        for i in range(1, N+1):
            curr = bin(i)[2:]
            # print(curr)
            if S.find(curr) == -1:
                return False
            
        return True

class Solution:
    def queryString(self, S: str, N: int) -> bool:
        if '1' not in S: return False
        res = set()
        cur = set()
        for s in S:
            if s == '0': 
                cur = {c * 2 for c in cur} | {0}
            else:
                cur = {c * 2 + 1 for c in cur} | {1}
            res |= cur
        for i in range(1, N+1):
            if i not in res: return False
        return True

class Solution:
    def queryString(self, S: str, M: int) -> bool:
        count = defaultdict(int)
        
        N = len(S)
        
        def f(ss):
            ans = 0
            nn = len(ss) - 1
            
            for ch in ss:
                if ch == '1':
                    ans += (1 << nn)
                nn -= 1
            
            return ans
            
        cnt = 0
        
        for n1 in range(N):
            for n2 in range(n1, N):
                if (n2 - n1 < 32):
                    val = f(S[n1:n2+1])
                    if val >= 1 and val <= M and count[val] == 0:
                        cnt += 1
                        count[val] = 1
                else:
                    break
        
        if cnt == M:
            return True
        return False

class Solution:
    def queryString(self, S: str, M: int) -> bool:
        count = defaultdict(int)
        
        N = len(S)
        
        def f(ss):
            ans = 0
            nn = len(ss) - 1
            
            for ch in ss:
                if ch == '1':
                    ans += (1 << nn)
                nn -= 1
            
            return ans
            
        cnt = 0
        
        for n1 in range(N):
            for n2 in range(n1, N):
                if (n2 - n1 < 32):
                    val = f(S[n1:n2+1])
                    if val >= 1 and val <= M and count[val] == 0:
                        cnt += 1
                        count[val] = 1
        
        if cnt == M:
            return True
        return False

class Solution:
    def queryString(self, S: str, N: int) -> bool:
        substrings = set()
        for i in range(len(S)):
            for j in range(i, len(S)+1):
                substrings.add(S[i:j])
        #print(substrings)
        for i in range(1,N+1):
            binN = str(bin(i))[2:]
            #print(binN)
            if binN in substrings:
                continue
            else:
                return False
        return True

class Solution:
    def queryString(self, S: str, N: int) -> bool:
        seen = set()
        if(len(S)<2):
            seen.add(S)
        for i in range(len(S)-1):
            for j in range(i+1,len(S)):
                if(S[i]=='0'):
                    seen.add(S[i+1:j+1])
                else:
                    seen.add(S[i:j+1])
        for i in range(1,N+1):
            binary = bin(i)[2:]
            if(binary not in seen):
                return False
        return True
        


class Solution:
    def queryString(self, S: str, N: int) -> bool:
        return all(bin(i)[2:] in S for i in range(N, N // 2, -1))

class Solution:
    def queryString(self, S: str, N: int) -> bool:
        st = set()
        
        for size in range(1, len(S)+1):
            for i in range(len(S) - size +1):
                st.add(S[i:i+size])
        
        #print(st)
        
        for i in range(1,N+1):
            #print(bin(i)[2:])
            if not bin(i)[2:] in st:
                
                return False
        
            
        return True

class Solution:
    def queryString(self, S: str, N: int) -> bool:
        
        dic = set()
        
        for i in range(len(S)):
            for l in range(len(S) - i):
                dic.add(S[i:i+l+1])
        for x in range(1, N+1):
            if str(bin(x)[2:]) not in dic:
                return False
        return True

from itertools import combinations 
class Solution:
    def queryString(self, S: str, N: int) -> bool:
        d=set()
        for i in range(0,len(S)+1):
            j=0
            end=i+1
            while end<len(S)+1:
                d.add(S[j:end])
                j=j+1
                end=end+1
        q=1
        for i in range(1,N+1):
            if bin(i)[2:] not in d:
                q=0
                break
        #print(type(bin(3)[2:]))
        return q



class Solution:
    def queryString(self, S: str, N: int) -> bool:
        n = len(S)
        for i in range(30,-1,-1):
            if N&(1<<i):
                msb = i
                break
        def get(msb):
            s =  set()
            num = 0
            x = 0
            if msb > 0:
                x = 1<<(msb-1)
            for i in range(n):
                if i == msb:
                    if S[i] == '1':
                        num += 1
                    if x < num <= N:
                        s.add(num)
                elif(i > msb):
                    # print(num,end=\" \")
                    if num&(1<<msb):
                        num -= (1<<msb)
                    num <<= 1
                    if S[i] == '1':
                        num += 1
                    if x < num <= N:
                        s.add(num)
                else:
                    if S[i]=='1':
                        num |= (1<<(msb- i))
            return s
        
        s = get(msb)
        p = 0
        if msb > 0:
            p = 1<<(msb-1)
        if msb > 0:
            s1 = get(msb-1)
            p = 0
            if msb > 1:
                p = 1<<(msb-2)
            for i in s1:
                s.add(i)
        # print(list(s),p)
        return len(s) == (N - p)
        
         
    


class Solution:
    def queryString(self, S: str, N: int) -> bool:
        # print(str(ord(N, 2)))
        
        def is_x_in(x):
            binary = []
            while x:
                binary.append(x % 2)
                x = x >> 1
            binary = ''.join(str(n) for n in reversed(binary))
            # print(binary)
            return S.find(binary) >= 0

        return all(is_x_in(x) for x in range(N+1))