刷题使我快乐，满脸开心.jpg

  • 来源：力扣（LeetCode）
  • 链接：https://leetcode.cn/problems/minimum-window-substring/
  • 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目

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

注意：

  • 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
  • 如果 s 中存在这样的子串，我们保证它是唯一的答案。

示例 1：

输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。

示例 2：

输入：s = "a", t = "a"
输出："a"
解释：整个字符串 s 是最小覆盖子串。

示例 3:

输入: s = "a", t = "aa"
输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。

提示：

  • m == s.length
  • n == t.length
  • 1 <= m, n <= 105
  • s 和 t 由英文字母组成

进阶：你能设计一个在 o(m+n) 时间内解决此问题的算法吗？

思路

最开始看到题目，想的就是哈希表存储字符计数，然后每次增加一个字符就看下是否满足，那么刚刚满足所有字符时就是最小覆盖子串了，不过当看到第一条注意以及示例时，意识到如果是字符存在重复的话，那么就有可能刚刚满足时并不是最小的覆盖子串。

但是，基于思路不能轻易浪费的念头，继续顺着这个思路思考下：

  • 如果此时覆盖子串并不是最短的，如果收缩？

如果需要收缩，右边界也就是遍历方向，如果遍历方向上满足了覆盖子串需求时，会立即触发判断，所以右边界并不需要收缩，反证法易得结论。

  • 左边界如果收缩？

对于如下例子来说，刚刚找到第一个覆盖子串时，其实可以让L指针继续右移到c处，此时才是最小覆盖子串，所以左边界收缩的特点就是找到覆盖子串后，逐步右移L，并同步的修改覆盖子串的字符计数信息，只要继续满足那就有可能会更新最小覆盖子串的长度，同时记录最小覆盖子串的位置坐标信息就好了

  • 能否简化操作。比如字符串中常见的，找到一个最小覆盖子串后，移动L到R位置，减少L的遍历次数？

不可，因为在移动过程中，可能错过覆盖子串，比如上图中，如果R右移两个位置后，其实L在第一个b的位置才是最小覆盖子串，但是如果移动L到R位置，将会错过此结果

至此，上代码，细节在备注里了~

代码

func minWindow(s string, t string) string {
	// 用哈希表存储子串字符及对应个数
	childCountMap := make(map[byte]int, 0)
	for _, b := range t {
		childCountMap[byte(b)]++
	}

	// 另用一个哈希表存储父串字符及对应个数
	countMap := make(map[byte]int, len(childCountMap))
	// 需要一个变量来记录最短长度方便比较；另需要两个变量来记录最短长度对应的位置
	resStartP, resEndP, minLen := -1, -1, math.MaxInt32
	// 记录s中覆盖t的子串的左边界，通过移动此位置来寻找最小的子串的左边界
	l := 0
	// s中覆盖t的子串的右边界，其实就是最开始满足覆盖t时遍历到的s的位置
	for r, b := range s {
		countMap[byte(b)]++
		for checkChild(countMap, childCountMap) && l <= r {
			// 注意长度是相减后+1
			if r-l+1 < minLen {
				minLen = r - l + 1
				// 这里记录的是起止下标，最终结果返回时候要注意
				// 需要截取的子串应该放的下标是[resStartP, resEndP+1]
				resStartP, resEndP = l, r
			}
			countMap[s[l]]--
			l++
		}
	}
	// 没有出现过覆盖子串，那就返回空
	if resStartP == -1 {
		return ""
	}
	return s[resStartP : resEndP+1]
}

func checkChild(countMap, childCountMap map[byte]int) bool {
	for k, v := range childCountMap {
		if countMap[k] < v {
			return false
		}
	}
	return true
}