算法笔记之滑动窗口——替换后的最长重复字符

滑动窗口的经典使用，有时候也叫作双指针，因为一左一右两个指针形成一个窗口。

题目描述

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

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

思路分析

本题可以先考虑 K=0 的情况，此时题目就变成了求解字符串中最长连续子串长度问题了。

我们先可以通过这个特例先了解一下滑动窗口的求解过程.

滑动窗口.jpg

K > 0 是基本思路相同，只要保证字符出现最大次数加上 K 小于等于窗口宽度就行。

因此首先需要一个变量来维护历史最大次数。

然后，我们维护一个数组 int[26] 来存储当前窗口中各个字母的出现次数，left 表示窗口的左边界，right表示窗口右边界。

• 窗口扩张：left 不变，right++
• 窗口滑动：left++，right++

最后的窗口大小 就是 重复字母的最长子串的长度。

Java代码

class Solution {
    public int characterReplacement(String s, int k) {
        int[] a = new int[26];
        int left = 0; // 左边界
        int right = 0; // 右边界
        int maxCharLength = 0; // 历史最大次数
        for(right = 0; right < s.length(); right++) {
            int c = s.charAt(right) - 'A';
            a[c]++;
            // 更新历史最大次数
            maxCharLength = a[c] > maxCharLength ? a[c] : maxCharLength;
            // 是否超出 
            if(right - left + 1 > maxCharLength + k) {
                // 超出则移动
                a[s.charAt(left)-'A']--;
                left++;
            }
        }
        return (s.length() - left);
     }
}