替换后的最长重复字符Java

文章发布较早，内容可能过时，阅读注意甄别。

# 题目

给你一个字符串 s 和一个整数 k 。你可以选择字符串中的任一字符，并将其更改为任何其他大写英文字符。该操作最多可执行 k 次。

在执行上述操作后，返回包含相同字母的最长子字符串的长度。

示例 1：

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

示例 2：

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

提示：

1 <= s.length <= 10⁵
s 仅由大写英文字母组成
0 <= k <= s.length

# 思路

滑动窗口

# 解法


class Solution {
    
    public int characterReplacement(String s, int k) {
        /*
        滑窗+字符统计:
        题意等价于:求一个最大长度的滑窗,该窗口内通过修改最多k个字符使得窗口内所有字符一样
        再进一步等价:达到要求修改的最少字符数 = 窗口长度 - 出现次数最多的字符个数 <= k
         */
        int len = s.length();
        int[] cntMap = new int[26];
        int res = 1;
        for (int l = 0, r = 0; r < len; r++) {
            ++cntMap[s.charAt(r) - 'A'];    // 新字母加入窗口
            while (!valid(cntMap, k)) { // 排除不符合条件的s[l]
                --cntMap[s.charAt(l) - 'A'];
                l++;
            }
            res = Math.max(res, r - l + 1); // 维护符合条件的最大窗口长度
        }
        return res;
    }

    // 判断是否能最多修改k个字符使得窗口内字母完全一样
    private boolean valid(int[] cntMap, int k) {
        int maxCnt = 0; // 出现频率最高的次数
        int total = 0;  // 字母总数
        for (int i = 0; i < 26; i++) {
            maxCnt = Math.max(maxCnt, cntMap[i]);
            total += cntMap[i];
        }
        return total - maxCnt <= k; // 需要修改的字母个数<=k表明符合要求
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

# 总结

分析出几种情况，然后分别对各个情况实现