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

Difficulty: interview

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 # Cannot be a string, as this is the de brujin length
        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:
        if len(s) < 2 ** k + k - 1:
            return False # Cannot be a string, as this is the de brujin length
        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 len(seen) == target


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:
        seen, total = set(), 2 ** k
        for i in range(len(s) - k + 1):
            if s[i:i+k] not in seen:
                seen.add(s[i:i+k])
                total -= 1
                if total == 0:
                    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:
        #     print(i)
        #     print(bin2dec(i))
            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:
        l = len(s)
        r = set()
        target = 2 ** k
        for i in range(0, l-k+1):
            r.add(
                s[i:i+k]
            )
        
            if len(r) == target:
                return True
        # else:
        return False

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


class Solution:
    def hasAllCodes(self, s: str, k: int) -> bool:
        if len(s) < k: return False
        for i in range(2**k):
            if bin(i)[2:].rjust(k, '0') 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):
            # print(s[i:i+k])
            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:
        set1 = set()
        for i in range(0, len(s) - k+1):
            set1.add(s[i:i+k])
        if(len(set1) >= 2**k):
            return True
        else:
            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)
        # print(result)
        if len(result)>=2**k:
            return True
        else:
            return False

class Solution:
  def hasAllCodes(self, s: str, k: int) -> bool:
      need = 1 << k # Equivalent to 2^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: # Found everything
            return True
      return False


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
        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:
        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
        return False

class Solution:
    def hasAllCodes(self, s: str, k: int) -> bool:
        hs = set()
        for i in range(len(s)-k+1):
            hs.add(s[i:i+k])
            if len(hs) == 2**k:
                return True
        print(hs)
        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:
        got = set() 
        required = 1 << k

        for i in range(len(s) - k+ 1): 
            if not s[i:i+k] in got: 
                got.add(s[i:i+k])
                required -= 1 
                if required == 0: 
                    return True
        
        return False

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)
        #print(num)
        mask = (1 << (k-1))  - 1
        #print(mask)
        for i in range(k, len(s)):
            num &= mask
            m = ord(s[i]) - ord('0')
            num = num * 2 + m
            d.add(num)
        #print(len(d))
        return len(d) >= (1<<k)


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

class Solution:
    def hasAllCodes(self, s: str, k: int) -> bool:
        h = 0
        nums = set()
        
        if len(s) < k:
            return False
        
        for i in range(k):
            h <<= 1
            h += (1 if s[i] == '1' else 0)
        nums.add(h)
        
        for i in range(k, len(s)):
            h <<= 1
            h -= (1 if s[i - k] == '1' else 0) << k
            h += (1 if s[i] == '1' else 0)
            nums.add(h)
            
        return len(nums) == (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]))
        # print(str_set)
        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


class Solution:
    # def hasAllCodes(self, s: str, k: int) -> bool:
    #     target_len = len(bin(k))-2
    #     for target in range(k, -1, -1):
    #         target = bin(target)[2:]
    #         target = (target_len-len(target))*'0'+target
    #         print (target)
    #         if s.find(target)==-1:
    #             return False
    #     return True
    
    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
        print (d)
        return False