leetcode76.最小覆盖子串

题目

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

注意：

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

用例

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

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

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

求解

/**
 * @param {string} s
 * @param {string} t
 * @return {string}
 */
var minWindow = function(s, t) {
    let need = new Object()
    for(let elem of t){
        need[elem]?need[elem]=need[elem]+1:need[elem]=1
    }
    let need_elem = Object.keys(need)
    let left = 0;
    let right = 0;
    let min_left = 0;
    let min_right = s.length;
    let flag = false
    while(right<s.length){
        need[s[right]]=need[s[right]]-1
        let manzu = true;
        for(let i=0;i<need_elem.length;i++){
            if(need[need_elem[i]]>0){
                manzu = false
            }
        }
        //当不满足的时候一直拉右边
        if(manzu==false){
            right++
        }else{
            flag = true
            let tmp_left = left
            let tmp_right = right
            //当满足的时候拉最左边，拉到最小为止
            while(left<=right){
                tmp_left = left
                tmp_right = right
                need[s[left]]=need[s[left]]+1

                let manzu2 = true;
                for(let i=0;i<need_elem.length;i++){
                    if(need[need_elem[i]]>0){
                        manzu2 = false
                    }
                }
                //如果仍然满足，则继续拉
                if(manzu2==true){
                    left++
                }else{
                    left++
                    //如果不满足了跳出循环
                    break
                }
            }
            if((tmp_right-tmp_left)<(min_right-min_left)){
                min_left = tmp_left
                min_right = tmp_right
            }
            right++
        }
    }
    if(flag==false){
        return ""
    }else{
        return s.slice(min_left,min_right+1)
    }
};