LeetCode Longest Repeating Character Replacement Given a string that consists of only uppercase English letters, you can replace any letter in the string with another letter at most k times. Find the length of a longest substring containing all repeating letters you can get after performing the above operations. Note: Both the string’s length and k will not exceed 10⁴. Example 1:

Input:
s = "ABAB", k = 2
Output:
4
Explanation:
Replace the two 'A's with two 'B's or vice versa.

Example 2:

Input:
s = "AABABBA", k = 1
Output:
4
Explanation:
Replace the one 'A' in the middle with 'B' and form "AABBBBA".
The substring "BBBB" has the longest repeating letters, which is 4.

---

给定一个字符串s，可以把s中最多k个字符换成另一个字符，问这样做之后，最大能得到多长的重复字符的字符串。 比如样例一s=”ABAB”,k=2，把两个A都改为B之后，所有字符都变成了B，长度为4。 本题使用滑动窗口来解。每次我们统计窗口内出现频率最多的字符，那么最好的办法就是把窗口内其他字符全换成最高频的字符，条件就是其他字符的数量要不超过k，这样替换的次数才不会超过k。 在滑动窗口的时候，如果其他字符的数量超过k了，则需要缩减窗口大小，也就是把窗口左端往右滑。 代码如下： [cpp] class Solution { public: int characterReplacement(string s, int k) { int ans = 0, n = s.size(); vector<int> count(26, 0); int start = 0; for (int end = 0; end < n; ++end) { ++count[s[end] – ‘A’]; while (end – start + 1 – *max_element(count.begin(), count.end()) > k) { –count[s[start++] – ‘A’]; } ans = max(ans, end – start + 1); } return ans; } }; [/cpp] 本代码提交AC，用时29MS。渐进复杂度应该是O(n^2)的。 讨论区还有O(n)的方法，但是我看了好久都没理解，为啥max不会减少，为啥返回的直接是s.length()-start。]]>