# 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).


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://hao-fu-1.gitbook.io/oj/multiple-pointers/sliding-window/dynamic-window/longest-repeating-character-replacement.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.