最小覆盖子串

难度：⭐⭐⭐⭐ Hard

考点

• 滑动窗口进阶
• 双哈希表计数
• 字节面试 Hard 高频题

题目描述

给你字符串 s 和 t，返回 s 中涵盖 t 所有字符的最小子串。如果不存在，返回空字符串 ""。

注意：t 中重复字符需要在窗口中全部包含（个数也要够）。

函数签名

func minWindow(s string, t string) string

示例

输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"

输入：s = "a", t = "a"
输出："a"

输入：s = "a", t = "aa"
输出：""（s 中只有一个 'a'，不够）

要求

1. 时间复杂度 O(n)，n = len(s)

提示

• need map：记录 t 中每个字符需要的个数
• window map：记录当前窗口内的字符个数
• matched 计数器：记录已经满足条件的字符种类数
• 右指针扩张找到可行解 → 左指针收缩找最优解

---

参考答案（Go）

点击展开参考答案

//go:build ignore

package answer

func minWindow(s string, t string) string {
	need := make(map[byte]int)
	for i := 0; i < len(t); i++ {
		need[t[i]]++
	}

	window := make(map[byte]int)
	left := 0
	matched := 0
	start, minLen := 0, len(s)+1

	for right := 0; right < len(s); right++ {
		c := s[right]
		if _, ok := need[c]; ok {
			window[c]++
			if window[c] == need[c] {
				matched++
			}
		}

		for matched == len(need) {
			if right-left+1 < minLen {
				minLen = right - left + 1
				start = left
			}
			d := s[left]
			if _, ok := need[d]; ok {
				if window[d] == need[d] {
					matched--
				}
				window[d]--
			}
			left++
		}
	}

	if minLen == len(s)+1 {
		return ""
	}
	return s[start : start+minLen]
}