76. 最小覆盖子串
难度困难2122
给你一个字符串 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 <= 105s和t由英文字母组成
进阶： 你能设计一个在 o(n) 时间内解决此问题的算法吗？
思路
/** * @param {string} s * @param {string} t * @return {string} */ var minWindow = function(s, t) { // 左右指针 let left = 0; let right = 0; const map = new Map() // 记录t字符串 for(let i of t) { map.set(i,map.has(i) ? map.get(i) + 1 : 1); } // 字母类型总数 let Types = map.size; // 返回字符串 let res = ''; while(right < s.length) { // 先跑right指针 let c = s[right]; if(map.has(c)) { map.set(c,map.get(c) - 1) if(map.get(c) == 0) Types--; } // 满足t字符串就跑left指针 while(Types == 0) { let newRes = s.substring(left,right+1); // 遇到更短的就更新res if(!res || newRes.length < res.length) { res = newRes; } // 跑left指针，知道left到right之间不满足t字符串 let c2 = s[left]; if(map.has(c2)) { map.set(c2,map.get(c2)+1); if(map.get(c2) == 1) Types++; } left++ } right++; } return res; };
