最小覆盖子串 · 最短通关小队

1func minWindow(s string, t string) string {
2    if len(t) == 0 || len(s) == 0 || len(t) > len(s) {
3        return ""
4    }
5    need := make(map[byte]int)
6    for i := 0; i < len(t); i++ {
7        need[t[i]]++
8    }
9    missing := len(t)
10    left := 0
11    start, minLen := 0, len(s)+1
12 
13    for right := 0; right < len(s); right++ {
14        c := s[right]
15        if need[c] > 0 {
16            missing--
17        }
18        need[c]--
19 
20        for missing == 0 {
21            if right-left+1 < minLen {
22                start = left
23                minLen = right - left + 1
24            }
25            lc := s[left]
26            need[lc]++
27            if need[lc] > 0 {
28                missing++
29            }
30            left++
31        }
32    }
33    if minLen == len(s)+1 {
34        return ""
35    }
36    return s[start : start+minLen]
37}

行级中文解释

• L14, L15

  need[c] > 0 表示这个字符还欠着，读到它可以还债，missing--

• L16

  need[c]-- 表示字符进入窗口；哪怕是多余的也要记录（会变成负数）

• L18

  missing == 0 表示窗口已经覆盖 t 的全部频次

• L24, L25

  收缩左边时 need[lc]++；若变回正数，说明移走了必要实例，窗口失效

• L25, L26

  need[lc] > 0 时 missing++，停止继续收缩