Задача: 1461. Check If a String Contains All Binary Codes of Size K
Сложность: medium

Дана бинарная строка s и целое число k, верните true, если каждый бинарный код длины k является подстрокой s. В противном случае верните false.

Пример:

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 indices 0, 1, 3 and 2 respectively.

👨‍💻 Алгоритм:

1⃣Определите количество возможных двоичных кодов длины k.

2⃣Создайте массив для отслеживания, какие коды были найдены. Итерируйте по строке s, вычисляя хэш для текущего окна длины k и обновляя массив отслеживания.

3⃣Возвращайте true, если все возможные коды найдены, иначе false.

😎 Решение:

class Solution {
    func hasAllCodes(_ s: String, _ k: Int) -> Bool {
        let need = 1 << k
        var got = [Bool](repeating: false, count: need)
        let allOne = need - 1
        var hashVal = 0
        let chars = Array(s)
        
        for i in 0..<chars.count {
            hashVal = ((hashVal << 1) & allOne) | (chars[i] == "1" ? 1 : 0)
            if i >= k - 1 && !got[hashVal] {
                got[hashVal] = true
                if got.allSatisfy({ $0 }) {
                    return true
                }
            }
        }
        return false
    }
}

Ставь 👍 и забирай 📚 Базу знаний