76. Minimum Window Substring

Hard

Description

給定兩個字串 s 和 t，找出 s 中包含 t 所有字元（含重複）的最短子字串。如果不存在則回傳空字串。

Example:

Input: s = “ADOBECODEBANC”, t = “ABC” Output: “BANC”

Intuition#

擴展右邊界直到視窗包含 t 的所有字元，然後收縮左邊界找最短的合法視窗。

先擴展右邊界，把字元「收集」進來，直到滿足條件
滿足條件後，嘗試收縮左邊界，看能不能找到更短的子字串
用 have / need 計數器追蹤「已經滿足幾種字元的需求」

Approaches#

1: Brute Force#

概念: 列舉所有子字串，檢查是否包含 t 的所有字元
時間複雜度: O(n² * m)，n 為 s 長度，m 為 t 長度
空間複雜度: O(m)

Brute Force 程式碼

class Solution {
    fun minWindow(s: String, t: String): String {
        if (t.length > s.length) return ""
        val tCount = mutableMapOf<Char, Int>()
        for (c in t) tCount[c] = tCount.getOrDefault(c, 0) + 1
        var result = ""
        for (i in s.indices) {
            val windowCount = mutableMapOf<Char, Int>()
            for (j in i until s.length) {
                windowCount[s[j]] = windowCount.getOrDefault(s[j], 0) + 1
                if (tCount.all { (k, v) -> windowCount.getOrDefault(k, 0) >= v }) {
                    if (result.isEmpty() || j - i + 1 < result.length) {
                        result = s.substring(i, j + 1)
                    }
                    break
                }
            }
        }
        return result
    }
}

⭐2: Sliding Window + Have/Need Counter#

概念: 用兩個 HashMap 和 have/need 計數器，擴展到滿足後收縮找最短
時間複雜度: O(n)
空間複雜度: O(m)，m 為 t 中不同字元數

class Solution {
    fun minWindow(s: String, t: String): String {
        if (t.isEmpty()) return ""
        val tCount = mutableMapOf<Char, Int>()
        for (c in t) tCount[c] = tCount.getOrDefault(c, 0) + 1

        val windowCount = mutableMapOf<Char, Int>()
        var have = 0
        val need = tCount.size
        var result = intArrayOf(-1, -1)
        var resultLen = Int.MAX_VALUE
        var left = 0

        for (right in s.indices) {
            val c = s[right]
            windowCount[c] = windowCount.getOrDefault(c, 0) + 1
            if (c in tCount && windowCount[c] == tCount[c]) {
                have++
            }
            while (have == need) {
                if (right - left + 1 < resultLen) {
                    resultLen = right - left + 1
                    result = intArrayOf(left, right)
                }
                val leftChar = s[left]
                windowCount[leftChar] = windowCount[leftChar]!! - 1
                if (leftChar in tCount && windowCount[leftChar]!! < tCount[leftChar]!!) {
                    have--
                }
                left++
            }
        }
        return if (resultLen == Int.MAX_VALUE) "" else s.substring(result[0], result[1] + 1)
    }
}

注意 have 只在字元頻率「剛好達到」需求時加 1，而不是每次加入字元都加。同理，收縮時只在頻率「剛好低於」需求時減 1。

🔑 Takeaways#

Pattern: 可變長度滑動視窗 + 條件滿足後收縮
關鍵技巧: have/need 計數器模式可以 O(1) 判斷視窗是否滿足條件，避免每次遍歷整個頻率表。這個模式適用於所有「包含某些元素」的視窗問題