# 0424. 替换后的最长重复字符

### 题目地址(424. 替换后的最长重复字符)

<https://leetcode-cn.com/problems/longest-repeating-character-replacement/>

### 题目描述

```
给你一个仅由大写英文字母组成的字符串，你可以将任意位置上的字符替换成另外的字符，总共可最多替换 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 题解仓库：<https://github.com/azl397985856/leetcode> 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。

关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。

![](https://p.ipic.vip/qceyie.jpg)


---

# 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://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/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.