給定兩個字串
s和t，找出s中包含t所有字元（含重複）的最短子字串。如果不存在則回傳空字串。
Example:
Input: s = “ADOBECODEBANC”, t = “ABC” Output: “BANC”
Intuition
TIP
擴展右邊界直到視窗包含 t 的所有字元，然後收縮左邊界找最短的合法視窗。
- 先擴展右邊界，把字元「收集」進來，直到滿足條件
- 滿足條件後，嘗試收縮左邊界，看能不能找到更短的子字串
- 用
have/need計數器追蹤「已經滿足幾種字元的需求」
Approaches
1. Brute Force — O(n² * m) / O(m)
- Idea: 列舉所有子字串，檢查是否包含 t 的所有字元
- Time:
O(n² * m)，n 為 s 長度，m 為 t 長度 - Space:
O(m)
Brute Force Code
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 — O(n) / O(m)
- Idea: 用兩個 HashMap 和 have/need 計數器，擴展到滿足後收縮找最短
- Time:
O(n) - Space:
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)
}
}WARNING
注意 have 只在字元頻率「剛好達到」需求時加 1，而不是每次加入字元都加。同理，收縮時只在頻率「剛好低於」需求時減 1。
🔑 Takeaways
- Pattern: 可變長度滑動視窗 + 條件滿足後收縮
- Key trick: have/need 計數器模式可以 O(1) 判斷視窗是否滿足條件，避免每次遍歷整個頻率表。這個模式適用於所有「包含某些元素」的視窗問題