76.最小覆盖子串

[chasingsnail]

给你一个字符串 S、一个字符串 T 。请你设计一种算法，可以在 O(n) 的时间复杂度内，从字符串 S 里面找出：包含 T 所有字符的最小子串。

 

示例：

输入：S = "ADOBECODEBANC", T = "ABC"
输出："BANC"

提示：

如果 S 中不存这样的子串，则返回空字符串 ""。
如果 S 中存在这样的子串，我们保证它是唯一的答案。

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

思路

维护一个对象来记录子串中字符出现的频率，当窗口内的子串满足条件时开始收缩 left，并记录子串。

/**
 * @param {string} s
 * @param {string} t
 * @return {string}
 */
var minWindow = function (s, t) {
  let result = ''

  let freq = {}
  for (const item of t) {
    freq[item] = freq[item] ? ++freq[item] : 1
  }

  const nLen = Object.keys(freq).length

  // let store = {}
  let count = 0

  let left = 0
  let right = 0

  while (right < s.length) {
    const curR = s[right]
    right++
    if (--freq[curR] === 0) {
      count++
    }

    while (count === nLen) {
      const curL = s[left]
      if ((result.length && right - left < result.length) || !result) {
        result = s.slice(left, right)
      }
      left++
      if (++freq[curL] > 0) {
        count--
      }
    }
  }

  return result
}