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

难度: 🌕🌕🌗

问题描述

---

解法

class Solution {
    public int characterReplacement(String s, int k) {
        // 思路：
        // 滑动窗口
        // 每次无论如何都会向右滑动一步，而左边界根据情况选择不滑动或者向右滑动一步
        // 判断依据在于条件：当前窗口长度[right - left + 1] > 出现次数最多的元素出现个数 + k[其他元素均需要修改为最多元素]
        int len = s.length();
        if(len == 1) {
            return 1;
        }
        // len > 1
        int left = 0;
        int right = 0;
        int count = 0; // 记录滑动窗口中出现次数最多的元素出现次数，不一定每次都是准确的
        int[] arr = new int[26]; // 记录各字符出现次数，更新 count 时用到

        while(right < len) {
            char c = s.charAt(right);
            int index = c - 'A';
            arr[index] ++;
            // right 加入进来后，有可能影响 count 的值
            // 只有影响后，count 才能保证是准确的；否则，count 不一定是当前窗口内的那个出现次数最多元素的次数，有虚高的情况
            count = Math.max(count, arr[index]); 

            // 判断是否有必要滑动左窗口
            if(right - left + 1 > count + k) {
                arr[s.charAt(left) - 'A'] --;
                left ++;
                // count 不准确的问题就出现在这里
                // 假设 count 所在元素包含原 left，但是现在 left 右移，而 count 并没有改变，从而导致 count 虚高
                // 但这里我们为什么没有判断是否需要更新 count 呢？
                // 分析：
                // 假设我们不更新 count，只有在 right - left + 1 > count + k 条件下才会进入该方法导致 count 不准确
                // 假设 left 正好是 count 的一部分，就这样导致 count 比准确值多了 1
                // 在下一轮中，right ++, left ++，即下一轮的窗口大小不变
                // 然后进入判断条件 count = Math.max(count, arr[index]) 
                // 若 count 在该判断中保持不变，那么仍然会进入 right - left + 1 > count + k 条件，进而窗口大小一直不变
                // 若 count 发生更新，那么 count 一定是最准确的，那么后续逻辑无任何问题
                // 因此可以看出，只有在发生 count 更新时，count 变得准确，逻辑无问题
                // count 发生虚高时，对窗口大小这一结果造不成任何影响，窗口大小始终保持整体右移的不变结果
                // 所以这里允许 count 短暂不一致的情况出现
            }
            right ++;
        }
        // right == len
        return right - left;
    }
}

---

输出