題目描述
給你一個僅由大寫英文字母組成的字符串，你可以將任意位置上的字符替換成另外的字符，總共可最多替換 k 次。在執行上述操作后，找到包含重復字母的最長子串的長度。
示例1
輸入：
s = "ABAB", k = 2
輸出：
4
解釋：
用兩個'A'替換為兩個'B',反之亦然。示例2
輸入：
s = "AABABBA", k = 1
輸出：
4
解釋：
將中間的一個'A'替換為'B',字符串變為 "AABBBBA"。
子串 "BBBB" 有最長重復字母, 答案為 4。提示 字符串長度和 k 不會超過 10^4。
題解
這題和之前做過的一題非常類似：
godweiyang：每日算法系列【LeetCode 1004】最大連續1的個數 III?zhuanlan.zhihu.com
只不過這題字符數量變成了 26 個。
方法和那題類似，都是用滑動窗口。用數組 count 記錄每個字母出現的次數，并且用變量 cmax 記錄窗口中出現次數最多的字母數量。
當前窗口是 [l, r] ，如果保留窗口中出現次數最多的字母，將其他字母全部替換為這個字母，那么替換次數就是
代碼
c++
class Solution {
public:int characterReplacement(string s, int k) {int n = s.size();vector<int> count(26, 0);int l = 0, r = 0, cmax = 0, res = 0;while (r < n) {cmax = max(cmax, ++count[s[r]-'A']);while (r - l + 1 - cmax > k)count[s[l++]-'A']--;res = max(res, r - l + 1);r++;}return res;}
};
python
class Solution:def characterReplacement(self, s: str, k: int) -> int:n = len(s)count = [0] * 26l, r, cmax, res = 0, 0, 0, 0while r < n:count[ord(s[r])-ord('A')] += 1cmax = max(cmax, count[ord(s[r])-ord('A')])while r - l + 1 - cmax > k:count[ord(s[l])-ord('A')] -= 1l += 1res = max(res, r - l + 1)r += 1return res后記
注意這里代碼實現上面有個很大的問題，就是右移左端點縮小窗口的時候， cmax 并沒有跟著減小，這樣為什么還是對的呢？這種情況下， cmax保存的其實是歷史出現次數最多的字母的次數。而你不改變 cmax ，就會導致中間過程中出現很多不符合題意的窗口，也就是實際要修改的數量大于 k 的窗口，但是因為你 cmax 偏大，算下來修改數量偏小，它又是符合題意的。不過不影響，這些錯誤的窗口的長度一定是小于你之前算到的正確窗口的長度的（如果大于了，那么 cmax 一定會被更新）。
下面解釋來自于algsCG：
因為我們只對最長有效的子字符串感興趣，所以我們的滑動窗口不需要收縮，即使窗口可能覆蓋無效的子字符串。我們可以通過在右邊添加一個字符來擴展窗口，或者將整個窗口向右邊移動一個字符。而且我們只在新字符的計數超過歷史最大計數（來自覆蓋有效子字符串的前一個窗口）時才增長窗口。也就是說，我們不需要精確的當前窗口的最大計數;我們只關心最大計數是否超過歷史最大計數;這只會因為新字符而發生。
![[國嵌攻略][132][串口驅動實現]](http://pic.xiahunao.cn/[國嵌攻略][132][串口驅動實現])
![[轉] vim自定義配置 和 在ubnetu中安裝vim](http://pic.xiahunao.cn/[轉] vim自定義配置 和 在ubnetu中安裝vim)
 PHP 隨筆---LAMP Linux基本操作 對文件、目錄的操作)
實體Bean的開發技術-建立與數據庫的連接)
