LC-1461 Medium LeetCode

1461. Check If a String Contains All Binary Codes of Size K

Hash Table String Bit Manipulation Rolling Hash Hash Function

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 57% Topics: Hash Table, String, Bit Manipulation, Rolling Hash, Hash Function

Reading material

Arrays & Hashing 12 min Strings 12 min Bit Manipulation 10 min

Reference solution (spoiler · python)

# Time:  O(n * k)
# Space: O(k * 2^k)

class Solution(object):
    def hasAllCodes(self, s, k):
        """
        :type s: str
        :type k: int
        :rtype: bool
        """
        return 2**k <= len(s) and len({s[i:i+k] for i in xrange(len(s)-k+1)}) == 2**k
    

# Time:  O(n * k)
# Space: O(2^k)
class Solution2(object):
    def hasAllCodes(self, s, k):
        """
        :type s: str
        :type k: int
        :rtype: bool
        """
        lookup = set()
        base = 2**k
        if base > len(s):
            return False
        num = 0
        for i in xrange(len(s)):
            num = (num << 1) + (s[i] == '1')
            if i >= k-1:
                lookup.add(num)
                num -= (s[i-k+1] == '1') * (base//2)
        return len(lookup) == base

Solution from kamyu104/LeetCode-Solutions · MIT