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

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

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

---

First completed : July 12, 2024

Last updated : July 13, 2024

---

Related Topics : Hash Table, String, Bit Manipulation, Rolling Hash, Hash Function

Acceptance Rate : 56.537 %

---

Solutions

• m1461 v1 Set.py
• m1461 v2 Set and Rolling Hash.py
• m1461 v3 Rolling Hash and Boolean Hashmap.py

Python

m1461 v1 Set.py

class Solution:
    def hasAllCodes(self, s: str, k: int) -> bool:
        found = set()

        for i in range(len(s) - k + 1) :
            found.add(s[i : i + k])
        
        return len(found) == 2 ** k

m1461 v2 Set and Rolling Hash.py

class Solution:
    def hasAllCodes(self, s: str, k: int) -> bool:
        found = set()
        current = int(s[:k], 2)
        found.add(current)
        for i in range(k, len(s)) :
            current = (2 * current) % (2 ** k) + (ord(s[i]) - ord('0'))
            found.add(current)

        return len(found) == 2 ** k

m1461 v3 Rolling Hash and Boolean Hashmap.py

class Solution:
    def hasAllCodes(self, s: str, k: int) -> bool:
        notFound = [True] * (2 ** k)
        current = int(s[:k], 2)
        notFound[current] = False
        for i in range(k, len(s)) :
            current = (2 * current) % (2 ** k) + (ord(s[i]) - ord('0'))
            notFound[current] = False

        return not any(notFound)