> For the complete documentation index, see [llms.txt](https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/424.longest-repeating-character-replacement.md).
# 0424. 替换后的最长重复字符
### 题目地址(424. 替换后的最长重复字符)
### 题目描述
```
给你一个仅由大写英文字母组成的字符串，你可以将任意位置上的字符替换成另外的字符，总共可最多替换 k 次。在执行上述操作后，找到包含重复字母的最长子串的长度。
注意：字符串长度 和 k 不会超过 104。
示例 1：
输入：s = "ABAB", k = 2
输出：4
解释：用两个'A'替换为两个'B',反之亦然。
示例 2：
输入：s = "AABABBA", k = 1
输出：4
解释：
将中间的一个'A'替换为'B',字符串变为 "AABBBBA"。
子串 "BBBB" 有最长重复字母, 答案为 4。
```
### 前置知识
*
### 公司
* 暂无
### 最长连续 1 模型
#### 思路
这道题其实就是我之前写的滑动窗口的一道题[【1004. 最大连续 1 的个数 III】滑动窗口（Python3）](https://leetcode-cn.com/problems/max-consecutive-ones-iii/solution/1004-zui-da-lian-xu-1de-ge-shu-iii-hua-dong-chuang/)的换皮题。字节跳动[2018 年的校招（第四批)](https://lucifer.ren/blog/2020/09/06/byte-dance-algo-ex/)也考察了这道题的换皮题。
这道题和那两道题差不多。唯一的不同是这道题是 **26 种可能**（因为每一个大写字母都可能是最终的最长重复子串包含的字母），而上面两题是一种可能。这也不难，枚举 26 种情况，取最大值就行了。
**最长连续 1 模型**可以直接参考上面的链接。其核心算法简单来说，就是**维护一个可变窗口，窗口内的不重复字符小于等于 k，最终返回最大窗口的大小即可。**
#### 关键点
* 最长连续 1 模型
#### 代码
* 语言支持：Python3
Python3 Code:
```python
class Solution:
def characterReplacement(self, s: str, k: int) -> int:
def fix(c, k):
ans = i = 0
for j in range(len(s)):
k -= s[j] != c
while i < j and k < 0:
k += s[i] != c
i += 1
ans = max(ans, j - i + 1)
return ans
ans = 0
for i in range(26):
ans = max(ans, fix(chr(ord("A") + i), k))
return ans
```
**复杂度分析**
令 n 为数组长度。
* 时间复杂度：$O(26 \* n)$
* 空间复杂度：$O(1)$
### 空间换时间
#### 思路
我们也可以用一个长度为 26 的数组 counts 记录每个字母出现的频率，如果窗口大小大于`最大频率+k`，我们需要收缩窗口。
这提示我们继续使用滑动窗口技巧。和上面一样，也是**维护一个可变窗口，窗口内的不重复字符小于等于 k，最终返回最大窗口的大小即可。**
#### 关键点
* 空间换时间
#### 代码
* 语言支持：Python3
Python3 Code:
```python
class Solution:
def characterReplacement(self, s: str, k: int) -> int:
if not s: return 0
counts = [0] * 26
i = most_fraq = 0
for j in range(len(s)):
counts[ord(s[j]) - ord("A")] += 1
most_fraq = max(most_fraq, counts[ord(s[j]) - ord("A")])
if i < j and j - i + 1 - most_fraq > k:
counts[ord(s[i]) - ord("A")] -= 1
i += 1
return j - i + 1
```
**复杂度分析**
令 n 为数组长度。
* 时间复杂度：$O(n)$
* 空间复杂度：$O(26)$
> 此题解由 [力扣刷题插件](https://leetcode-pp.github.io/leetcode-cheat/?tab=solution-template) 自动生成。
力扣的小伙伴可以[关注我](https://leetcode-cn.com/u/fe-lucifer/)，这样就会第一时间收到我的动态啦\~
以上就是本文的全部内容了。大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库： 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
