20220509

最小覆盖子串

输入："XDOYEZODEYXNZ","XYZ"
返回值："YXNZ"

function minWindow( S ,  T ) {
    let ret = ""
    if(T.length>S.length) return ret
    // 记录T中字符
    let storeMap = getStrMap()

    //  第一次 拿到一个窗口
    let [l,r] = getWindowLR(S,0);
    ret = S.substring(l,r+1)
    // 当 窗口占满整个S时
    if(r==S.length-1) return  ret  
    // 以第一个窗口大小为基准平移，获取窗口内最短长度的字符串
    for(let i=r+1;i < S.length;i++) {
        let str = S.charAt(i);
        let [mL,mR] = getWindowLR(S.substring(l, i+1), l)
        if(mL !=-1 && mR != -1 && mR-mL<ret.length)   ret=S.substring(mL, mR+1)

        l++ 
    }
    // map格式 '字符' => 数量,
    function getStrMap () {
        let map = new Map()
        for(let item of T) {
           map.set(item, (map.get(item)||0) + 1)
        }
        return map
    }
    // 在S中遍历，当目标子串所有元素都被使用时，即windowMap.size == 0时，返回子串的左右下标
    function getWindowLR(S,dx) {
        //  因为map复制是浅克隆，会影响原map，故需要重新建一个
        le在S中遍历，获取第一个满足所有条件字符串左右下标 = getStrMap()
        let l=-1, r=-1,flag=false;
        for(let i=0;i<S.length;i++) {
            let str = S.charAt(i);
            // 过滤无关的字符
            if(!storeMap.has(str)) continue;
            if (!flag) {
                l=i
                flag = true
            };
            if (windowMap.has(str)) {
                let count= windowMap.get(str);
                count-1>0 ?  windowMap.set(str, count-1): windowMap.delete(str)
            }
            if(windowMap.size == 0) r = i

            if(l!=-1&&r!=-1) return [l+dx,r+dx]
        }
        return [l,r]
    }

    return ret
}