LeetCode中怎么替換后的最長(zhǎng)重復(fù)字符串

題目描述：

給你一個(gè)僅由大寫(xiě)英文字母組成的字符串，你可以將任意位置上的字符替換成另外的字符，總共可最多替換 k 次。在執(zhí)行上述操作后，找到包含重復(fù)字母的最長(zhǎng)子串的長(zhǎng)度。

注意：字符串長(zhǎng)度 和 k 不會(huì)超過(guò) 10^4。

示例 1：

輸入：s = "ABAB", k = 2
輸出：4
解釋：用兩個(gè)'A'替換為兩個(gè)'B',反之亦然。

示例 2：

輸入：s = "AABABBA", k = 1
輸出：4
解釋：
將中間的一個(gè)'A'替換為'B',字符串變?yōu)?"AABBBBA"。
子串 "BBBB" 有最長(zhǎng)重復(fù)字母, 答案為 4

思路分析：

一看到最長(zhǎng)字符串就想到滑動(dòng)窗口。

算法流程：

• 右邊界先移動(dòng)找到一個(gè)滿足題意的可以替換 k 個(gè)字符以后，所有字符都變成一樣的當(dāng)前看來(lái)最長(zhǎng)的子串，直到右邊界納入一個(gè)字符以后，不能滿足的時(shí)候停下；
• 然后考慮左邊界向右移動(dòng)，左邊界只須要向右移動(dòng)一格以后，右邊界就又可以開(kāi)始向右移動(dòng)了，繼續(xù)嘗試找到更長(zhǎng)的目標(biāo)子串；
• 替換后的最長(zhǎng)重復(fù)子串就產(chǎn)生在右邊界、左邊界交替向右移動(dòng)的過(guò)程中。

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        from collections import defaultdict
        d = defaultdict(int)
        l = 0
        maxn = 0
        for r in range(len(s)):
            d[s[r]] += 1
            maxn = max(maxn, d[s[r]])
            if r - l + 1 > maxn + k:  # bc it is for loop, r += 1 is later than if clause
                d[s[l]] -= 1
                l += 1
        return len(s) - l

class Solution {
    public int characterReplacement(String s, int k) {
        int len=s.length();
        if(len<2){
            return len;
        }
        char[] chararray=s.toCharArray();
        int left=0,right=0;
        int maxCount=0,res=0;
        int[] freq = new int[26];
        while(right<len){
            freq[chararray[right]-'A']++;
            maxCount=Math.max(maxCount,freq[chararray[right]-'A']);
            right++;
            if(right-left>maxCount+k){
                freq[chararray[left]-'A']--;
                left++;
            }
            res=Math.max(res,right-left);
            
        }
        return res;
    }
}