> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/multiple-pointers/sliding-window/dynamic-window/longest-repeating-character-replacement.md).

# 424. Longest Repeating Character Replacement

Given a string `s` that consists of only uppercase English letters, you can perform at most `k` operations on that string.

In one operation, you can choose **any** character of the string and change it to any other uppercase English character.

Find the length of the longest sub-string containing all repeating letters you can get after performing the above operations.

**Note:**\
Both the string's length and k will not exceed 104.

**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.
```

## Thoughts

数组元素由\[A, Z]组成，问能把其中k个字符全替换成任一字符后最长的重复子串长度。argmax + substring => dynamic window 或DP。遍历并以当前字符s\[r]为底，当窗口内出现最多的子符对应的次数mx加上允许替换的字母数k 超过窗口宽度时说明窗口可以全部填满成窗口该字符，即mx + k > r - l + 1时，窗口还可以更长；mx + k < r - l + 1时说明能构成的最长的重复字母长度不足以覆盖整个窗口，因为多了一位s\[r]，左边压缩一位。分析当r右移时，l是否会回弹，两种情况：1. s\[r] == 最多频率的字符，l往左移保证(mx + 1) + k < r - (l - 1) + 1 == mx + k < r - l + 1，不能覆盖；2. s\[r]不为最多频率的字符，mx + (k + 1) < r - (l - 1) + 1，不能覆盖。因此满足动态窗口题解所须『压缩后不回弹』条件。

## Code

```java
class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        l, freq, res = 0, [0] * 26, 0
        for r, c in enumerate(s):
            freq[ord(c) - ord('A')] += 1
            if r - l + 1 > max(freq) + k: 
                freq[ord(s[l]) - ord('A')] -= 1  
                l += 1 
            res = max(res, r - l + 1)
        return res
            
```

```java
class Solution {
    public int characterReplacement(String s, int k) {
        if (s.length() == 0) {
            return 0;
        }
        int[] amount = new int[26];
        int l = 0, r = 0, res = 0;      

        while (r < s.length()) {
            amount[s.charAt(r) - 'A']++;
            int maxCount = 0;
            for (int i = 0; i < 26; i ++) {
                maxCount = Math.max(maxCount, amount[i]);
            }

            if (maxCount + k < r - l + 1) {
                // Do not extend the window size.
                // Move the whole window to the right
                amount[s.charAt(l) - 'A']--;
                l++;
            }

            res = Math.max(res, r - l + 1);
            r++;
        }

        return res;
    }
}
```

## Analysis

时间复杂度O(n), 空间O(1).