# 424 Longest Repeating Character Replacement

## 424. [Longest Repeating Character Replacement](https://leetcode.com/problems/longest-repeating-character-replacement/description/)

## 1. Question

Given a string that consists of only uppercase English letters, you can replace any letter in the string with another letter at mostktimes. Find the length of a longest substring containing all repeating letters you can get after performing the above operations.

**Note:**\
Both the string's length andkwill 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.
```

## 2. Implementation

**(1) Two Pointer + Hash**

思路: 这道题的本质是问找到一个最长的substring满足，该substring的长度减substring中最多重复的character的个数是小于等于k的。所以我们维护一个变量maxCount, 从左向右扫s， maxCount记录目前最多重复的character的个数，当substring的长度减去maxCount的值大于k时，我们需要更新substring的起点。

```java
class Solution {
    public int characterReplacement(String s, int k) {
        if (s.length() <= k) {
            return s.length();
        }

        int start = 0, end = 0, maxCount = 0, maxLen = 0;
        int[] map = new int[256];

        while (end < s.length()) {
            ++map[s.charAt(end)];
            maxCount = Math.max(maxCount, map[s.charAt(end)]);
            ++end;

            if (end - start - maxCount > k) {
                --map[s.charAt(start)];
                ++start;
            }
            maxLen = Math.max(maxLen, end - start);
        }
        return maxLen;
    }
}
```

## 3. Time & Space Complexity

**Two Pointer + Hash:** 时间复杂度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://protegejj.gitbook.io/algorithm-practice/leetcode/two-pointers/424-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.