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

Source: leetcode | Difficulty: MEDIUM
Tags: String algorithms

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:
		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, N: int) -> bool:
		substrings = set()
		for i in range(len(S)):
			for j in range(i, len(S) + 1):
				substrings.add(S[i:j])
		for i in range(1, N + 1):
			binN = str(bin(i))[2:]
			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])
		for i in range(1, N + 1):
			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
		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:
					if num & 1 << msb:
						num -= 1 << msb
					num <<= 1
					if S[i] == '1':
						num += 1
					if x < num <= N:
						s.add(num)
				elif 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)
		return len(s) == N - p


class Solution:

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

		def is_x_in(x):
			binary = []
			while x:
				binary.append(x % 2)
				x = x >> 1
			binary = ''.join((str(n) for n in reversed(binary)))
			return S.find(binary) >= 0
		return all((is_x_in(x) for x in range(N + 1)))