---
# System prepended metadata

title: 0424. Longest Repeating Character Replacement
tags: [Leetcode, Sliding Window, Medium]

---

# 0424. Longest Repeating Character Replacement
###### tags: `Leetcode` `Medium` `Sliding Window`
Link: https://leetcode.com/problems/longest-repeating-character-replacement/
## 思路 $O(N)$ $O(1)$
Sliding Window
在移动的过程中，记录每个字母出现的频率
并且每次找最大的频率，如果r-l+1-maxCnt>k，就说明在现在的window里要替换的不止k个，因此要挪动l
**优化：并不需要每次在array里面找最大的，只要保留曾经出现过的最大值即可**
虽然现在maxCnt不一定一直是array里面的最大值，但是并不影响结果，因为maxCnt对应的一定是最长的长度，**不会因为maxCnt给大了，就错过最长的长度**
## Code
```java=
class Solution {
    public int characterReplacement(String s, int k) {
        int[] count = new int[26];
        int l = 0, r = 0;
        int maxLen = 0;
        int maxCnt = 0;
        while(r < s.length()){
            // count[s.charAt(r)-'A']++;
            // int maxCnt = 0;
            // for(int i = 0;i < 26;i++){
            //     maxCnt = Math.max(maxCnt, count[i]);
            // }
            maxCnt = Math.max(maxCnt, ++count[s.charAt(r)-'A']);
            if(r-l+1-maxCnt>k){
                count[s.charAt(l++)-'A']--;
            }
            maxLen = Math.max(maxLen, r-l+1);
            r++;
        }
        return maxLen;
    }
}
```