1461. Check if a String Contains all Binary Codes of Size K

Medium

Description

給定二進位字串 s 和整數 k，判斷 s 是否包含所有長度為 k 的二進位字串作為子字串。長度為 k 的二進位字串共有 2^k 個。

Example:

Input: s = “00110110”, k = 2 Output: true （包含 “00”, “01”, “10”, “11” 所有 2-bit 字串）

Intuition#

核心思路：用 HashSet 收集 s 中所有長度為 k 的子字串，若 Set 大小達到 2^k 即回傳 true。

總共有 2^k 個不同的 k-bit 字串
滑動窗口取所有長度 k 的子字串加入 Set
一旦 Set.size == 2^k 就可以提前回傳 true

Approaches#

1: HashSet of Strings#

概念: 直接用字串 HashSet 儲存所有長度 k 的子字串
時間複雜度: O(n * k) - 每次取子字串 O(k)
空間複雜度: O(2^k * k) - 最多存 2^k 個長度 k 的字串

class Solution {
    fun hasAllCodes(s: String, k: Int): Boolean {
        if (s.length < k) return false
        val total = 1 shl k  // 2^k
        val seen = HashSet<String>()

        for (i in 0..s.length - k) {
            seen.add(s.substring(i, i + k))
            if (seen.size == total) return true
        }
        return false
    }
}

⭐2: Rolling Hash with BitSet#

概念: 用整數 Rolling Hash 取代字串，將 k-bit 子字串直接解讀為整數，用 HashSet 或 boolean 陣列記錄
時間複雜度: O(n) - 每次滑動 O(1) 更新 hash
空間複雜度: O(2^k) - boolean 陣列或 HashSet

class Solution {
    fun hasAllCodes(s: String, k: Int): Boolean {
        if (s.length < k) return false
        val total = 1 shl k
        val mask = total - 1
        val seen = BooleanArray(total)
        var count = 0
        var hash = 0

        for (i in s.indices) {
            hash = ((hash shl 1) or (s[i] - '0')) and mask

            if (i >= k - 1) {
                if (!seen[hash]) {
                    seen[hash] = true
                    count++
                    if (count == total) return true
                }
            }
        }
        return false
    }
}

注意 k 的值上限：若 k 很大（例如 20），2^k = 1048576，boolean 陣列仍可接受。但若 s.length < 2^k + k - 1，必然不可能包含所有 code，可以提前返回 false。

🔑 Takeaways#

Pattern: 固定長度子字串的完整性檢查 -> Sliding Window + HashSet/Rolling Hash
關鍵技巧: 二進位字串天然適合用整數 Rolling Hash，左移加入新 bit、mask 移除舊 bit，每次 O(1) 更新