0424. Longest Repeating Character Replacement¶
题目信息¶
- 题号:
0424
- 难度:
Medium
- 主题:
大写字符串、至多
k次替换、连续子串、相同字符- 原题:
- 重点:
只能替换字符不能重排、选择的是连续子串、替换后子串内所有字符相同、操作次数可以少于
k
题目重述¶
给定只包含大写英文字母的字符串 s 和非负整数 k。最多可以选择 k 个位置,把其中的字符替换成任意大写英文字母。返回经过这些操作后,字符串中能够出现的最长连续同字符子串长度。
s.length 位于 [1, 10^5],k 位于 [0, s.length]。不要求必须使用完全部 k 次替换;不能删除、插入或重新排列字符。只返回最大长度,不需要返回修改后的字符串或子串位置。
自建示例¶
一次替换扩展末尾重复段:
输入:s = "ABACCC",k = 1
输出:4
解释:把紧邻三个 C 的 A 替换为 C,可以得到连续四个 C;一次替换无法形成长度为 5 的同字符子串。
不允许替换:
输入:s = "AABBA",k = 0
输出:2
解释:不能改变任何字符,最长现有重复段是 AA 或 BB,长度均为 2。
窗口长度减去最高频次就是所需替换数¶
维护一个滑动窗口和窗口内每个大写字母的频次。若把窗口中出现次数最多的字符保留为目标字符,其余字符都替换掉即可使整个窗口相同,所需次数为 windowLength - maxFrequency。当这个数量超过 k 时,移动左端并归还字符;否则用窗口长度更新答案。
maxFrequency 可以只增不减:它是窗口历史上的上界,偶尔比当前窗口真实最高频次大只会让窗口暂时显得更宽,不会让最终记录的最大合法长度超过真实答案;左端仍会在必要时继续收缩。
C++ 实现¶
class Solution {
public:
int characterReplacement(std::string s, int k) {
std::array<int, 26> frequency{};
int left = 0;
int maxFrequency = 0;
int answer = 0;
for (int right = 0;
right < static_cast<int>(s.size()); ++right) {
maxFrequency = std::max(
maxFrequency, ++frequency[s[right] - 'A']);
while (right - left + 1 - maxFrequency > k) {
--frequency[s[left] - 'A'];
++left;
}
answer = std::max(answer, right - left + 1);
}
return answer;
}
};
代码分析¶
窗口保持“可由至多 k 次替换统一”的条件,最长合法窗口就是答案;字符频次固定为 26,左右指针各走一次。时间复杂度为 O(n),额外空间为 O(1)。