Given a binary string s and an integer k.
Return True if every binary code of length k is a substring of s. Otherwise, return False.
 
Example 1:
Input: s = "00110110", k = 2
Output: true
Explanation: The binary codes of length 2 are "00", "01", "10" and "11". They can be all found as substrings at indicies 0, 1, 3 and 2 respectively.

Example 2:
Input: s = "00110", k = 2
Output: true

Example 3:
Input: s = "0110", k = 1
Output: true
Explanation: The binary codes of length 1 are "0" and "1", it is clear that both exist as a substring. 

Example 4:
Input: s = "0110", k = 2
Output: false
Explanation: The binary code "00" is of length 2 and doesn't exist in the array.

Example 5:
Input: s = "0000000001011100", k = 4
Output: false

 
Constraints:

1 <= s.length <= 5 * 10^5
s consists of 0's and 1's only.
1 <= k <= 20

Source: leetcode | Difficulty: MEDIUM
Tags: String algorithms

Bit manipulation

Data structures

Starter code: class Solution:
    def hasAllCodes(self, s: str, k: int) -> bool:
        

Solutions:
class Solution:

	def hasAllCodes(self, s: str, k: int) -> bool:
		if len(s) < 2 ** k + k - 1:
			return False
		target = 2 ** k
		seen = set()
		cur_len = 0
		for end in range(k, len(s) + 1):
			chunk = s[end - k:end]
			if chunk not in seen:
				cur_len += 1
				seen.add(chunk)
				if cur_len == target:
					return True
		return False


class Solution:

	def hasAllCodes(self, s: str, k: int) -> bool:
		a = 2 ** k
		k_string = set()
		for i in range(len(s) - k + 1):
			if s[i:i + k] not in k_string:
				k_string.add(s[i:i + k])
				if len(k_string) == a:
					return True
		return False


class Solution:

	def hasAllCodes(self, s: str, k: int) -> bool:
		nums = set()
		for i in range(0, len(s) - k + 1):
			nums.add(s[i:i + k])
			if len(nums) == 2 ** k:
				return True
		return False


class Solution:

	def hasAllCodes(self, s: str, k: int) -> bool:
		from itertools import permutations
		c = dict()
		count = 0
		for i in range(0, len(s) - k + 1):
			out = ''
			for j in range(i, i + k):
				out = out + s[j]
			if out not in c:
				c[out] = True
				count = count + 1
			if count == pow(2, k):
				return True
		return False


class Solution:

	def hasAllCodes(self, s: str, k: int) -> bool:
		bins = {}
		numbers = {}
		st = s
		print(k)

		def bin2dec(a):
			val = 0
			for i in range(len(a)):
				if a[i] == '1':
					val += pow(2, len(a) - 1 - i)
			return val
		for i in range(len(st) - k + 1):
			if st[i:i + k] in bins:
				continue
			else:
				bins[st[i:i + k]] = 1
		for i in bins:
			numbers[bin2dec(i)] = 1
		c = 0
		for i in range(pow(2, k)):
			if i in numbers:
				c += 1
		print((c, k))
		if c == pow(2, k):
			return True
		else:
			return False


class Solution:

	def hasAllCodes(self, s: str, k: int) -> bool:

		def Hash_Function(b):
			num = list(b)
			num.reverse()
			total = 0
			increment = 1
			for item in num:
				if item == '1':
					total = total + increment
					increment = increment * 2
				else:
					increment = increment * 2
					continue
			return total
		start = 0
		end = k
		buckets = []
		buckets = set(buckets)
		while end <= len(s):
			num = Hash_Function(s[start:end])
			buckets.add(num)
			start += 1
			end += 1
		if len(buckets) == 2 ** k:
			return True
		else:
			return False


class Solution:

	def hasAllCodes(self, s: str, k: int) -> bool:
		check = []
		for kk in range(2 ** k):
			t = bin(kk)[2:]
			check.append('0' * (k - len(t)) + t)
		ss = set()
		for i in range(k, len(s) + 1):
			ss.add(s[i - k:i])
		for t in check:
			if t not in ss:
				return False
		return True


class Solution:

	def hasAllCodes(self, s: str, k: int) -> bool:
		for i in range(2 ** k):
			bin_value = bin(i)[2:] if len(bin(i)[2:]) == k else '0' * (k - len(bin(i)[2:])) + bin(i)[2]
			if bin_value not in s:
				return False
		return True


def binary_strings(k):
	res = []
	stack = ['']
	while stack:
		s = stack.pop()
		if len(s) == k:
			res.append(s)
		else:
			stack.append(s + '0')
			stack.append(s + '1')
	return res

class Solution:

	def hasAllCodes(self, s: str, k: int) -> bool:
		seen = set()
		for i in range(0, len(s) - k + 1):
			seen.add(s[i:i + k])
		for bs in binary_strings(k):
			if bs not in seen:
				return False
		return True


class Solution:

	def hasAllCodes(self, s: str, k: int) -> bool:
		for i in range(2 ** k):
			ss = bin(i)[2:].zfill(k)
			if ss not in s:
				return False
		return True


from itertools import product

class Solution:

	def hasAllCodes(self, s: str, k: int) -> bool:
		p = product('01', repeat=k)
		for sub in p:
			if s.find(''.join(sub)) == -1:
				return False
		return True


class Solution:

	def hasAllCodes(self, s: str, k: int) -> bool:
		codes = {format(i, f'0{k}b'): False for i in range(2 ** k)}
		for i in range(len(s) - k + 1):
			ss = s[i:i + k]
			if ss in codes:
				codes[ss] = True
		return all(codes.values())


class Solution:

	def hasAllCodes(self, s: str, k: int) -> bool:
		arr_2 = ['0', '1']
		m = k - 1
		while m != 0:
			arr_2 = ['0' + i for i in arr_2] + ['1' + i for i in arr_2]
			m -= 1
		for i in range(2 ** k):
			if arr_2[i] in s:
				continue
			else:
				return False
		return True


class Solution:

	def hasAllCodes(self, s: str, k: int) -> bool:

		def binary_code_of_length_k(k):
			if k == 1:
				return ['0', '1']
			t = binary_code_of_length_k(k - 1)
			return ['0' + i for i in t] + ['1' + i for i in t]
		k_string = binary_code_of_length_k(k)
		for i in k_string:
			if s.find(i) == -1:
				return False
		return True


class Solution:

	def hasAllCodes(self, s: str, k: int) -> bool:
		codes = set((format(i, f'0{k}b') for i in range(2 ** k)))
		found = [False for i in range(2 ** k)]
		for i in range(len(s) - k + 1):
			if s[i:i + k] in codes:
				found[int(s[i:i + k], base=2)] = True
		return all(found)


class Solution:

	def hasAllCodes(self, s: str, k: int) -> bool:
		combinations = 2 ** k
		seen = set()
		for i in range(len(s) - k + 1):
			temp = s[i:i + k]
			if temp not in seen:
				seen.add(temp)
				combinations -= 1
				if combinations == 0:
					return True
		return False


class Solution:

	def hasAllCodes(self, s: str, k: int) -> bool:
		if len(s) < k:
			return False
		substring_set = set()
		need = 1 << k
		for start in range(len(s) - k + 1):
			ss = s[start:start + k]
			if ss not in substring_set:
				substring_set.add(ss)
				need -= 1
				if need == 0:
					return True
		return False


class Solution:

	def hasAllCodes(self, s: str, k: int) -> bool:
		st = set()
		for i in range(k, len(s) + 1):
			st.add(s[i - k:i])
			if len(st) == 1 << k:
				break
		return len(st) == 1 << k


from itertools import permutations

class Solution:

	def hasAllCodes(self, s: str, k: int) -> bool:
		d = set()
		for i in range(len(s) - k + 1):
			if s[i:i + k] not in d:
				d.add(s[i:i + k])
				if len(d) == 2 ** k:
					return True
		return False


class Solution:

	def hasAllCodes(self, s: str, k: int) -> bool:
		result = set()
		for i in range(len(s) - k + 1):
			val = s[i:i + k]
			result.add(val)
		if len(result) >= 2 ** k:
			return True
		else:
			return False


class Solution:

	def hasAllCodes(self, s: str, k: int) -> bool:
		need = 1 << k
		got = set()
		for i in range(k, len(s) + 1):
			tmp = s[i - k:i]
			if tmp not in got:
				got.add(tmp)
				need -= 1
				if need == 0:
					return True
		return False


class Solution:

	def hasAllCodes(self, s: str, k: int) -> bool:
		l = len(s)
		r = set()
		for i in range(0, l - k + 1):
			r.add(s[i:i + k])
			if len(r) == 2 ** k:
				return True
		for i in product(['0', '1'], repeat=k):
			_ = ''.join(i)
			if _ not in r:
				return False
		return True


class Solution:

	def hasAllCodes(self, s: str, k: int) -> bool:
		if k >= len(s):
			return False
		d = set()
		num = 0
		for i in range(k):
			m = ord(s[i]) - ord('0')
			num = num * 2 + m
		d.add(num)
		mask = (1 << k - 1) - 1
		for i in range(k, len(s)):
			num &= mask
			m = ord(s[i]) - ord('0')
			num = num * 2 + m
			d.add(num)
		return len(d) >= 1 << k


class Solution:

	def hasAllCodes(self, s: str, k: int) -> bool:
		str_set = set()
		for i in range(len(s) - k + 1):
			str_set.add(str(s[i:i + k]))
		for i in range(2 ** k):
			formatter = '{0:0%sb}' % str(k)
			if formatter.format(i) not in str_set:
				return False
		return True


class Solution:

	def hasAllCodes(self, s: str, k: int) -> bool:
		arr = list(s)
		arr = [ord(el) - 48 for el in arr]
		length = 0
		n = len(s)
		curr = 0
		h = {}
		for i in range(n - 1, -1, -1):
			length += 1
			if length > k:
				length -= 1
				curr = curr >> 1
			if arr[i] == 1:
				curr = 1 << length - 1 | curr
			if length == k:
				h[curr] = True
		return len(h) == pow(2, k)


class Solution:

	def hasAllCodes(self, s: str, k: int) -> bool:
		need = 2 ** k
		_new = set()
		for i in range(len(s) - k + 1):
			var = s[i:i + k]
			if var not in _new:
				_new.add(var)
				need -= 1
			if need == 0:
				return True
		return False