替换后的最长重复字符(java实现)

力扣 424. 替换后的最长重复字符

题目说明

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

字符串长度和 k 不会超过 10的4次方。

示例

例1

1
2
3

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

例2

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

笔者理解

此题是一道数组求解算法问题，在力扣题库中被定义为中等题。

解法

当笔者阅读完此题后，发现此题需要用到窗口的概念，我们只需要保证窗口内的元素符合题意，经过窗口移动，然后再比较存储窗口的最大区间值即可。

窗口：有头有尾的一段区间。

符合题意：窗口内元素符合有限个数字符替换后变成同一字母

实现

public int characterReplacement(String s, int k) {
        int result = 0;
        int front = 0;
        //窗口的前端
        int []dict = new int[26];
        //当前窗口各字符出现的次数
        int maxNum = 0;
        //窗口重复字母的最大数
        int temp;
        //记录当前字母在字母表的第几位
        for (int i = 0; i < s.length(); i++) {
            temp = s.charAt(i)-'A';
            dict[temp]++;
            //当前字母出现次数加一
            maxNum = Math.max(dict[temp],maxNum);
            //窗口内出现次数最多的字母数
            while(i-front+1-maxNum>k){
                //如果窗口宽度减最多字母数大于可修正的字符数
                //移动窗口，并删除边框前端元素
                dict[s.charAt(front)-'A']--;
                front++;
            }
            result = Math.max(result,i-front+1);
            //伴随窗口移动记录最大值
        }
        return result;
    }