LCP-424 替换后的最长重复字符

题目回顾

题目详情

给你一个仅由大写英文字母组成的字符串，你可以将任意位置上的字符替换成另外的字符，总共可最多替换 k 次。在执行上述操作后，找到包含重复字母的最长子串的长度。

注意：字符串长度 和 k 不会超过 104。

示例 1：

输入：s = "ABAB", k = 2
输出：4
解释：用两个'A'替换为两个'B',反之亦然。

示例 2：

输入：s = "AABABBA", k = 1
输出：4
解释：
将中间的一个'A'替换为'B',字符串变为 "AABBBBA"。
子串 "BBBB" 有最长重复字母, 答案为 4。

---

Discussion | Solution

解法思路

本题采用滑动窗口和双指针的思路来进行解题。（太久没做题了，标准题解看来半天才看懂）

从题目的要求来分析其实很好理解。要求最长的子串，那么肯定这个串是连续的（废话），所以就很适合用滑动窗口的方法，一个窗口从左移到右，寻找出符合条件的最大窗口长度，即为题目所求。本题的关键就在于如何控制窗口左右边界的移动。

先来看看怎样的窗口子串是符合条件的：要找到尽可能长的重复串，毋庸置疑，肯定是找出现次数最多的字母，同时你还可以最多把k的其他字符也变成它。所以符合条件的子串一定满足：

窗口长度 - 同一字母最大出现次数 <= k

窗口移动的规则即为：

• 右指针++
• 若区间内窗口长度 - 同一字母最大出现次数 > k左指针++

以上操作保证了窗口长度只增不减，这样最后的窗口长度就是结果

比如那s = "AABABBA", k = 1的例子

初始时左右指针都指向0

↓

AABABBA

↑

---

窗口长度(1) - 1 < 1，r++

↓

AABABBA

↑

---

窗口长度(2) - 2 < 1，r++

↓

AABABBA

​ ↑

---

窗口长度(3) - 2 <= 1，r++

↓

AABABBA

​ ↑

---

窗口长度(4) - 3 <= 1，r++

↓

AABABBA

​ ↑

---

窗口长度(5) - 3 > 1，r++, l++

↓

AABABBA

​ ↑

---

窗口长度(5) - 3 > 1，r++, l++

​ ↓

AABABBA

​ ↑

最终结果为 $r-l = 4$

代码实现

/*
 * @lc app=leetcode.cn id=424 lang=java
 *
 * [424] 替换后的最长重复字符
 */

class Solution {
    public int characterReplacement(String s, int k) {

        int[] cnt = new int[26];

        int l = 0;
        int r = 0;
        int maxn = 0; // 窗口内出现最多次的字母个数
        for (; r < s.length(); r++) {
            cnt[s.charAt(r)-'A']++;
            maxn = Math.max(maxn, cnt[s.charAt(r)-'A']);
            if(r-l+1-maxn>k){
                cnt[s.charAt(l)-'A']--; // 窗口最左边的字符出去了
                l++;
            }
        }
        return r-l;
    }
}

时间复杂度O(n)，空间复杂度O(|M|)