2021-02-02：力扣424. 替換後的最長重複字元。如何用程式碼實現？

福哥答案2021-02-02：

雙指標

我們可以列舉字串中的每一個位置作為右端點，然後找到其最遠的左端點的位置，滿足該區間內除了出現次數最多的那一類字元之外，剩餘的字元（即非最長重複字元）數量不超過 kk 個。

這樣我們可以想到使用雙指標維護這些區間，每次右指標右移，如果區間仍然滿足條件，那麼左指標不移動，否則左指標至多右移一格，保證區間長度不減小。

雖然這樣的操作會導致部分割槽間不符合條件，即該區間內非最長重複字元超過了 kk 個。但是這樣的區間也同樣不可能對答案產生貢獻。當我們右指標移動到盡頭，左右指標對應的區間的長度必然對應一個長度最大的符合條件的區間。

實際程式碼中，由於字串中僅包含大寫字母，我們可以使用一個長度為 2626 的陣列維護每一個字元的出現次數。每次區間右移，我們更新右移位置的字元出現的次數，然後嘗試用它更新重複字元出現次數的歷史最大值，最後我們使用該最大值計算出區間內非最長重複字元的數量，以此判斷左指標是否需要右移即可。

注意點：

1.滑動視窗只會變大。不會變小。

2.每迴圈一次，右指標一定右滑一次。左指標可能右滑一次，可能不滑動。

3.最大字元數，是各個歷史視窗的最大字元數。

程式碼用golang編寫，程式碼如下：

func characterReplacement(s string, k int) int {    sLen := len(s)    //記錄次數的字典表    dict := make([]int, 256)    //記錄視窗的最大字元數，可能是歷史視窗最大字元數    maxCount := 0    L := 0    for R := 0; R < sLen; R++ {        dict[s[R]]++        if maxCount < dict[s[R]] {            maxCount = dict[s[R]]        }        //左指標要麼右滑一次，要麼不滑。也就是說，滑動視窗只會變大，不會變小        if R-L+1-maxCount > k {            dict[s[L]]--            L++        }    }    return sLen - L}

執行結果如下：

***

[力扣：424. 替換後的最長重複字元](https://leetcode-cn.com/problems/longest-repeating-character-replacement/)