這是leetcode上面一題Hard難度．題目如下

給兩個字串S跟T，請從S中找到包含T的全部字母的最短字串(順序不論)，如果沒有S沒有這樣的字串，就返回空字串．

例如 S = “ADBECFEBANC” ,T=”ABC”，則包含A B C三個字母的最短字串是 “BANC”

如果用暴力解法，那大概如下

for(i in 0..s.length){
        for(j in i+1 ..s.length){
            if(包含t所有字母){
						//更新答案
            }
        }
    }

不過很明顯，這個演算法的時間複雜度是n^2，不夠好，我們改用昨天學到的滑動視窗來試試看

整體的思路是這樣的

1.在起始字串S中使用雙指標的左右指標技巧，初始化left = right =0，把索引左閉右開的區間[left,right)稱為一個視窗

2.先不斷增加right的指標擴大視窗，直到視窗中的字串符合題目要求，也就是包含了目標字串T中的所有字元

3.停止增加right，改為增加left，這樣會縮小視窗，直到視窗中的字串不再符合題目的要求，也就是缺少了目標字串T中的某個字元．這時，每次變更left時，都要更新一輪結果

4.不停重複2. 跟3.的兩步驟，直到right到達了字串S的盡頭．

整個觀念是這樣的，我們在2.之中先找到一個可行解，然後在3.中優化這個可行解．這樣就能找到一個最短字串．然後我們輪流移動left跟right前進，而視窗大小增增減減，而且不斷向右邊移動，在滑動過程中找尋到的各種答案再來比較，這就是滑動視窗名字的由來

好的，接下來我們來時做看看，首先，先初始化兩個HashMap，分別紀錄視窗中的字元跟需要湊齊的字元．

val need = HashMap<Char,Int>()//需要湊齊的字元
val window = HashMap<Char,Int>()//視窗中的字元

然後初始化左右指標，注意區間[left,right)是左閉右開，因此初始化時視窗裡面是空的．valid我們用來代表視窗中買足need條件的字元個數，當valid的數字跟need.length相同時，代表視窗已經滿足題目的條件，找到一個完全覆蓋字串t的字串

var left = 0
var right = 0
var valid = 0
while(right<s.length){
		//開始滑動
}

有了初始條件，我們接下來思考以下四個問題:

1.當移動right來擴大視窗，也就是加入字元時，應該要更新哪些資料呢?

2.什麼條件達到了，right就先停止移動，改為開始移動left縮小視窗?

3.當移動left來縮小視窗，也就是移除字元時，應該要更新哪些資料呢?

4.結果應該在擴大視窗時，或是縮小視窗時更新?

在這個問題，如果一個字元進入了視窗，那我們應該增加window計數器，而當字元離開視窗，那們我們應該減少window計數器．這樣解決了1.3.兩題

在valid滿足need條件，也就是我們找到了一個解，開始尋找最佳解，就應該收縮視窗，同時更新答案，這就是2.4.兩題的答案

好了，有了這些材料，我們來組合出答案吧

fun minWindow(s: String, t: String):String {
    val need = HashMap<Char, Int>()
    t.forEach { need[it] = need.getOrDefault(it,0)+1 }//初始化湊齊的字元陣列
    val window = HashMap<Char, Int>()
    var left = 0
    var right = 0
    var valid = 0
    var ansStart = 0//記錄答案位置的起點
    var ansLength = Int.MAX_VALUE //記錄答案位置的長度
    while (right < s.length) {
        //c是即將移入視窗的字元
        val c = s[right]
        //右移視窗
        right++
        if(need.containsKey(c)){//更新因為右移視窗，視窗內資料變化
            window[c] = window.getOrDefault(c,0)+1
            if(window[c] == need[c]){
                valid++
            }
        }

        //判斷是否要開始縮小視窗左側
        while(valid == need.size){
            //在這裡檢查答案 看要不要更新
            if(right-left< ansLength){
                ansStart = left
                ansLength = right-left
            }
            //d是即將移出視窗的字元
            val d = s[left]
            //左移視窗
            left++
            if(need.containsKey(d)){//更新因為左移視窗，視窗內資料變化
                if(window[d] == need[d]){
                    valid--
                }
                window[d] = window.getOrDefault(d,0)-1
            }
        }
    }
    return if(ansLength == Int.MAX_VALUE){
        ""
    }else{
        s.substring(ansStart,ansStart+ansLength)
    }
}

我們用個測資來驗證看看吧

val s = "ADBECFEBANC"
val t = "ABC"
println(minWindow(s,t))

執行的結果如下

這題有點難度，不過多讀幾次應該就能理解其中的思路了，明天我們會再來看看幾題題目．