26、最小覆盖子串

题目描述

https://leetcode-cn.com/problems/minimum-window-substring/

解题思路

• 先找出所有包含T所有字符的子串
• 返回长度最小的子串

解题步骤

• 用双指针维护一个滑动窗口
• 移动右指针，找到包含T所有字符的子串，移动左指针，尽量减少包含T的子串的长度
• 循环上述过程，找出包含T所有字符的最小子串

代码实现

/**
 * @param {string} s
 * @param {string} t
 * @return {string}
 */
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)
    }
    console.log(need) // 罗列出t的所有字符和个数
    let needNum = need.size
    let result = ''
    while (r < s.length) {
        const c = s[r]
        if (need.has(c)) {
            need.set(c, need.get(c) - 1)
            if (need.get(c) === 0) needNum--
        }
        while (needNum === 0) { // 当子串包含t中所有字符时b 
            // console.log(s.substring(l, r + 1)) // 所有满足条件的子串
            const newResult = s.substring(l, r + 1)
            if (!result || newResult.length < result.length) result = newResult
            const c2 = s[l]
            if (need.has(c2)) {
                need.set(c2, need.get(c2) + 1)
                if (need.get(c2) === 1) needNum++
            }
            l++
        }
        r++
    }
    return result
};

时间复杂度： O(n+m) m是t的长度，n是s的长度
空间复杂度： O(k) k是t里面不同字符的个数