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