424. 替换后的最长重复字符
题目描述
输入一个由大写英文字母构成的字符串 s 和一个整数 k。
每次操作可以选一个位置，把那里的字符换成任意大写字母。操作总数不超过 k 次。
操作结束后，返回所有字符全都相同的子串中最长的长度。
示例 1
输入：s = "ABAB", k = 2 输出：4
解释：把两个 'A' 都改成 'B'（或反过来），整个串变成同一字母，长度为 4。
示例 2
输入：s = "AABABBA", k = 1 输出：4
解释：把下标 3 的 'A' 改成 'B'，得到 "AABBBBA"，其中 "BBBB" 长度为 4。
数据范围
1 <= s.length <= 10^5s只含大写英文字母。0 <= k <= s.length
解题思路：滑动窗口（最大频次）
一个窗口能改成同一字母，当且仅当“窗口长度 - 窗口内出现最多的字母次数” <= k。right 每步右移，用 maxf 记录历史上见过的最大频次。一旦窗口不合法，left 只右移一格，窗口整体平移、长度不变。因为只有 maxf 变大时答案才可能变大，所以窗口长度只增不减，最后的窗口长度 len(s) - left 就是答案。
为什么正确
窗口长度 right - left + 1 始终等于目前找到的最长合法长度（或再大 1 后立即被平移修正）；窗口只会变长或平移，从不变短。
复杂度分析
时间 O(n)，额外空间 O(26)。
易错点
窗口不合法时不用 while 一直收缩，也不用在移出字符后重新计算 maxf。maxf 偏大只会让窗口暂时保持长度，不会得到错误的更大答案。但要记住最终窗口里的内容不一定合法，只有它的长度是答案。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def characterReplacement(self, s: str, k: int) -> int:
cnt = collections.Counter()
left = maxf = 0
for right, c in enumerate(s):
cnt[c] += 1
maxf = max(maxf, cnt[c])
if right - left + 1 - maxf > k:
cnt[s[left]] -= 1
left += 1
return len(s) - leftclass Solution {
public int characterReplacement(String s, int k) {
int[] cnt = new int[26];
int left = 0, maxf = 0;
for (int right = 0; right < s.length(); right++) {
int c = s.charAt(right) - 'A';
cnt[c]++;
maxf = Math.max(maxf, cnt[c]);
if (right - left + 1 - maxf > k) {
cnt[s.charAt(left) - 'A']--;
left++;
}
}
return s.length() - left;
}
}class Solution {
public:
int characterReplacement(string s, int k) {
vector<int> cnt(26, 0);
int left = 0, maxf = 0;
for (int right = 0; right < (int)s.size(); right++) {
int c = s[right] - 'A';
cnt[c]++;
maxf = max(maxf, cnt[c]);
if (right - left + 1 - maxf > k) {
cnt[s[left] - 'A']--;
left++;
}
}
return (int)s.size() - left;
}
};func characterReplacement(s string, k int) int {
cnt := [26]int{}
left, maxf := 0, 0
for right := 0; right < len(s); right++ {
c := s[right] - 'A'
cnt[c]++
maxf = max(maxf, cnt[c])
if right-left+1-maxf > k {
cnt[s[left]-'A']--
left++
}
}
return len(s) - left
}var characterReplacement = function(s, k) {
const cnt = new Array(26).fill(0);
let left = 0, maxf = 0;
for (let right = 0; right < s.length; right++) {
const c = s.charCodeAt(right) - 65;
cnt[c]++;
maxf = Math.max(maxf, cnt[c]);
if (right - left + 1 - maxf > k) {
cnt[s.charCodeAt(left) - 65]--;
left++;
}
}
return s.length - left;
};function characterReplacement(s: string, k: number): number {
const cnt = new Array<number>(26).fill(0);
let left = 0, maxf = 0;
for (let right = 0; right < s.length; right++) {
const c = s.charCodeAt(right) - 65;
cnt[c]++;
maxf = Math.max(maxf, cnt[c]);
if (right - left + 1 - maxf > k) {
cnt[s.charCodeAt(left) - 65]--;
left++;
}
}
return s.length - left;
}其他解法
主解法一次扫描，靠历史最大频次保证窗口只增不减；枚举字母法多扫描 26 遍，但每一步的合法性都容易验证。
解法 2：枚举目标字母 时间 O(Σ·n)，空间 O(1)
枚举最终窗口里保留的字母 ch（共 26 种）。对每个 ch 做一次滑动窗口：other 记录窗口内不等于 ch 的字符数。other 超过 k 时右移左端点。所有窗口长度的最大值就是答案。
每个窗口的合法条件很明确，不需要理解“maxf 不回退”这个技巧，更容易证明正确。要对每个字母各扫描一遍，常数是主解法的 26 倍。
class Solution:
def characterReplacement(self, s: str, k: int) -> int:
best = 0
for ch in set(s):
left = other = 0
for right, c in enumerate(s):
if c != ch:
other += 1
while other > k:
if s[left] != ch:
other -= 1
left += 1
best = max(best, right - left + 1)
return bestclass Solution {
public int characterReplacement(String s, int k) {
int n = s.length(), best = 0;
for (char ch = 'A'; ch <= 'Z'; ch++) {
int left = 0, other = 0;
for (int right = 0; right < n; right++) {
if (s.charAt(right) != ch) other++;
while (other > k) {
if (s.charAt(left) != ch) other--;
left++;
}
best = Math.max(best, right - left + 1);
}
}
return best;
}
}class Solution {
public:
int characterReplacement(string s, int k) {
int n = s.size(), best = 0;
for (char ch = 'A'; ch <= 'Z'; ch++) {
int left = 0, other = 0;
for (int right = 0; right < n; right++) {
if (s[right] != ch) other++;
while (other > k) {
if (s[left] != ch) other--;
left++;
}
best = max(best, right - left + 1);
}
}
return best;
}
};func characterReplacement(s string, k int) int {
n, best := len(s), 0
for ch := byte('A'); ch <= 'Z'; ch++ {
left, other := 0, 0
for right := 0; right < n; right++ {
if s[right] != ch {
other++
}
for other > k {
if s[left] != ch {
other--
}
left++
}
if right-left+1 > best {
best = right - left + 1
}
}
}
return best
}var characterReplacement = function(s, k) {
const n = s.length;
let best = 0;
for (let c = 65; c <= 90; c++) {
const ch = String.fromCharCode(c);
let left = 0, other = 0;
for (let right = 0; right < n; right++) {
if (s[right] !== ch) other++;
while (other > k) {
if (s[left] !== ch) other--;
left++;
}
best = Math.max(best, right - left + 1);
}
}
return best;
};function characterReplacement(s: string, k: number): number {
const n = s.length;
let best = 0;
for (let c = 65; c <= 90; c++) {
const ch = String.fromCharCode(c);
let left = 0, other = 0;
for (let right = 0; right < n; right++) {
if (s[right] !== ch) other++;
while (other > k) {
if (s[left] !== ch) other--;
left++;
}
best = Math.max(best, right - left + 1);
}
}
return best;
}