Задача: 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 {
    function hasAllCodes($s, $k) {
        $need = 1 << $k;
        $got = array_fill(0, $need, false);
        $allOne = $need - 1;
        $hashVal = 0;
        
        for ($i = 0; $i < strlen($s); $i++) {
            $hashVal = (($hashVal << 1) & $allOne) | ($s[$i] - '0');
            if ($i >= $k - 1 && !$got[$hashVal]) {
                $got[$hashVal] = true;
                $need--;
                if ($need == 0) {
                    return true;
                }
            }
        }
        return false;
    }
}

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