76. 最小覆盖子串 (opens new window)

Description

Difficulty: 困难

Related Topics: 哈希表 (opens new window), 字符串 (opens new window), 滑动窗口 (opens new window)

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

注意：

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

示例 1：

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

示例 2：

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

示例 3:

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

提示：

• 1 <= s.length, t.length <= 10⁵
• s 和 t 由英文字母组成

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

Solution

Language: JavaScript

/**
 * @param {string} s
 * @param {string} t
 * @return {string}
 * 子串强调了[连续性]
 * T中可能包含重复字符
 * 1.暴力解法
 * 枚举输入字符串S的所有长度大于等于T的子串
 * 逐个判断这些子串中，哪些子串覆盖了字符串T的所有字符；
 * 在枚举的过程中，记录符合条件的，长度最短的那个子串。
 * 
 * 如何判断S的子串包含了T中的所有字符？
 * 参考做法：分别统计S的子串和T中每个字符出现的次数，然后逐个比对。
 * 字符频数数组
 */
// 滑动窗口：
// 1.什么时候移动右边界：当前窗口内的字符串，没有覆盖到子串，右边界越出数组边界，程序可以退出
// 2.什么时候移动左边界：当前窗口的字符串已经覆盖到子串，需要把窗口尽可能缩小，当继续缩小后不满足题意得时刻，就是满足的一个答案
// 3. 多个答案需要比较字符串长度
// 4. 因此需要使用unordered_map记录字符个数
// 5. helper辅助函数，用来比较窗口内是否完全覆盖子串，当窗口某个字符频次小于子串对应字符，false

// 1.创建左指针，右指针
// 2.将输入t的所有字符存入，map中
// 3.建立循环，直到右指针到s字符串长度结束
// 4.逐位移动右指针
// 5.如果need中有当前右指针的字符，need中当前右指针字符对应的value - 1
// 6.如果当前右指针字符对应的value === 0 needType -= 1
// 7.当needType === 0时候说明已经找到符合要求的子串开始处理左指针

var minWindow = function(s, t) {
 let l = 0
 let r = 0
 const need = new Map()
 for(let c of t) {
  need.set(c, need.has(c) ? need.get(c) + 1 : 1)
 }

 let needType = need.size
 let res = ''
 while (r < s.length) {
  let c = s[r]
  if (need.has(c)) {
   need.set(c, need.get(c) - 1)
   if (need.get(c) === 0) needType -= 1
  }

  while (needType === 0) {
   const newRes = s.substring(l, r + 1)
   if (!res || newRes.length < res.length) res = newRes

   const c2 = s[l]
   if (need.has(c2)) {
    need.set(c2, need.get(c2) + 1)
    if (need.get(c2) === 1) needType += 1
   }
   l += 1
  }
  r += 1
 }
 return res
}