###### tags: `Leetcode` `medium` `sliding window` `python` `c++`

# 424. Longest Repeating Character Replacement

## [題目連結:] https://leetcode.com/problems/longest-repeating-character-replacement/description/

## 題目:
You are given a string ```s``` and an integer ```k```. You can choose any character of the string and change it to any other uppercase English character. You can perform this operation at most ```k``` times.

Return the length of the longest substring containing the same letter you can get after performing the above operations.

**Example 1:**

Input: s = "ABAB", k = 2
Output: 4
Explanation: Replace the two 'A's with two 'B's or vice versa.

**Example 2:**

Input: s = "AABABBA", k = 1
Output: 4
Explanation: Replace the one 'A' in the middle with 'B' and form "AABBBBA".
The substring "BBBB" has the longest repeating letters, which is 4.

## 解題想法:
* 此題為給一字符串，有k次隨意置換任何字符的機會，求最長的重複字符串
* Sliding Window:
* tail: 每次向右移動滿足可替換k個字，持續擴張直到不能滿足
* head: 向右移動，每當head右移一個，tail即可繼續向右移動找更長字串
* 所需參數:
* head=0
* tail=0
* max_cur=0 #紀錄目前出現最多次的字符數量
* res=0
* count=[0]* 26 #紀錄26個字母出現數
* Sliding Window基本流程:

	while tail<len(數組):
		Step1. 紀錄數組[tail]
		Step2. 判斷不合法，將數組[head]處理並head+=1右移
		Step3. 更新res
		Step4. tail+=1 右移

* 套用此題，對 Step2 核心:
* 需判斷若當前連續距離(tail-head+1)，減掉max_cur後，大於可以替換的萬能k數量
* 則表示tail已經飽和不能再往前進，須讓head移動才能讓tail繼續往後探索

## Python:

class Solution(object):
    def characterReplacement(self, s, k):
        """
        :type s: str
        :type k: int
        :rtype: int
        """
        #Sliding Window
        #tail向右移動滿足可替換k個字，持續擴張直到不能滿足
        #head向右移動，每當head右移一個 tail即可繼續向右移動找更長字串
        head=0
        tail=0
        max_cur=0 #紀錄目前出現最多次的字符
        res=0
        count=[0]*26 #紀錄26個字母出現數
        while tail<len(s):
            #ord('A')=65
            count[ord(s[tail])-65]+=1 #紀錄出現次數
            max_cur=max(max_cur,count[ord(s[tail])-65])
            #若連續距離-max_cur多過於可以替換的萬能k數量 
            #表示tail已經飽和  該讓head移動好讓tail繼續探索
            if (tail-head+1)-max_cur > k:
                count[ord(s[head])-65]-=1
                head+=1
            res = max(res,tail-head+1)
            tail+=1
        return res
            
result = Solution()
s="AABCABBB"
k=2
ans=result.characterReplacement(s,k)
print(ans)

## C++:

class Solution {
public:
    int characterReplacement(string s, int k) {
        int n=s.size(), head=0, tail=0, max_cur=0, res=0;
        vector<int> count(26,0);
        while (tail<n){
            count[s[tail]-'A']+=1;
            max_cur=max(max_cur, count[s[tail]-'A']);
            if ((tail-head+1)-max_cur > k){
                count[s[head]-'A']-=1;
                head+=1;
            }
            res=max(res,tail-head+1);
            tail+=1;
        }
        return res;
    }
};