题目描述
这是 LeetCode 上的 424. 替换后的最长重复字符 ，难度为 中等。
Tag : 「双指针」、「滑动窗口」
给你一个仅由大写英文字母组成的字符串，你可以将任意位置上的字符替换成另外的字符，总共可最多替换 k 次。
在执行上述操作后，找到包含重复字母的最长子串的长度。
注意：字符串长度 和 k 不会超过 10410^4104。
示例 1：
输入：s = "ABAB", k = 2 输出：4 解释：用两个'A'替换为两个'B',反之亦然。 复制代码
示例 2：
输入：s = "AABABBA", k = 1 输出：4 解释： 将中间的一个'A'替换为'B',字符串变为 "AABBBBA"。 子串 "BBBB" 有最长重复字母, 答案为 4。 复制代码
滑动窗口
令 l 为符合条件的子串的左端点，r 为符合条件的子串的右端点。
使用 cnt 统计 [l,r] 范围的子串中每个字符串出现的次数。
对于合法的子串而言，必然有 sum(所有字符的出现次数) - max(出现次数最多的字符的出现次数）= other(其他字符的出现次数) <= k。
当找到这样的性质之后，我们可以对 s 进行遍历，每次让 r 右移并计数，如果符合条件，更新最大值；如果不符合条件，让 l 右移，更新计数，直到符合条件。
代码：
class Solution { public int characterReplacement(String s, int k) { char[] cs = s.toCharArray(); int[] cnt = new int[26]; int ans = 0; for (int l = 0, r = 0; r < s.length(); r++) { // cnt[cs[r] - 'A']++; int cur = cs[r] - 'A'; cnt[cur]++; // while (!check(cnt, k)) cnt[cs[l++] - 'A']--; while (!check(cnt, k)) { int del = cs[l] - 'A'; cnt[del]--; l++; } ans = Math.max(ans, r - l + 1); } return ans; } boolean check(int[] cnt, int k) { int max = 0, sum = 0; for (int i = 0; i < 26; i++) { max = Math.max(max, cnt[i]); sum += cnt[i]; } return sum - max <= k; } } 复制代码
- 时间复杂度：使用
l和r指针对s进行单次扫描，复杂度为 O(n)O(n)O(n)；check方法是对长度固定的数组进行扫描，复杂度为 O(1)O(1)O(1)。整体复杂度为 O(n)O(n)O(n)。 - 空间复杂度：使用了固定长度的数组进行统计。复杂度为 O(1)O(1)O(1)
最后
这是我们「刷穿 LeetCode」系列文章的第 No.724 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先将所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour…
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
