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

布满荆棘的人生 2022-10-26 12:59 67阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODE5OTc3MA_size_16_color_FFFFFF_t_70]  
[官方题解][Link 1]

public class Solution {
        
    
        public int characterReplacement(String s, int k) {
        
            int len = s.length();
            if (len < 2) {
        
                return len;
            }
    
            char[] charArray = s.toCharArray();
            int left = 0;
            int right = 0;
    
            int res = 0;
            int maxCount = 0;
            int[] freq = new int[26];
            // [left, right) 内最多替换 k 个字符可以得到只有一种字符的子串
            while (right < len){
        
                freq[charArray[right] - 'A']++;
                // 在这里维护 maxCount，因为每一次右边界读入一个字符，字符频数增加，才会使得 maxCount 增加
                maxCount = Math.max(maxCount, freq[charArray[right] - 'A']);
                right++;
    
                if (right - left > maxCount + k){
        
                  	// 说明此时 k 不够用
                    // 把其它不是最多出现的字符替换以后，都不能填满这个滑动的窗口，这个时候须要考虑左边界向右移动
                    // 移出滑动窗口的时候，频数数组须要相应地做减法
                    freq[charArray[left] - 'A']--;
                    left++;
                }
                res = Math.max(res, right - left);
            }
            return res;
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODE5OTc3MA_size_16_color_FFFFFF_t_70]: /images/20221024/8809bea7688a4642a18761057d3bdb06.png
[Link 1]: https://leetcode-cn.com/problems/longest-repeating-character-replacement/solution/ti-huan-hou-de-zui-chang-zhong-fu-zi-fu-eaacp/