LeetCode_滑动窗口_中等_424.替换后的最长重复字符

偏执的太偏执、 2023-10-06 23:19 21阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

给你一个字符串 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 <= 105  
s 仅由大写英文字母组成  
0 <= k <= s.length

来源：力扣（LeetCode）  
链接：https://leetcode.cn/problems/longest-repeating-character-replacement

## 2.思路 ##

（1）滑动窗口  
思路参考[该LeetCode用户题解][LeetCode]。

① 如果使用滑动窗口来解决本题的话，那么最关键的问题在于如何判断窗口 \[left, right\] 内的字符串是否可以通过题目中描述的操作使得该字符串包含的字母相同。这里”题目中描述的操作“指**选择字符串中的任一字符，并将其更改为任何其他大写英文字符（该操作最多可执行 k 次）**。

② 该用户提供的思路是将 **sum(所有字符的出现次数) - max(出现次数最多的字符的出现次数）= other(其他字符的出现次数)** 与 k 进行比较。将出现次数最多的字符记为 c，  
如果前者小于等于后者，则说明**其它字符可以在 k 次替换内变成字符 c**，那么滑动窗口内的字符就全部相等；  
如果前者大于等于后者，则说明**其它字符无法在 k 次替换内变成字符 c**，此时可以缩小窗口，即 left++；

③ 上面的判断可以封装到一个函数中，传入的参数为数组 cnt（记录窗口内每个字符出现的次数） 和 k，返回值为 sum - max <= k。

## 3.代码实现（Java） ##

//思路1————滑动窗口
    class Solution {
        
        public int characterReplacement(String s, int k) {
        
            //res 为替换后的包含相同字母的最长子字符串的长度，初始值为 0
            int res = 0;
            //将字符串转换为对应的字符数组，方便后续的遍历
            char[] cs = s.toCharArray();
            /*
                cnt 统计窗口 [left, right] 中每个字符出现的次数
                cnt[0]表示滑动窗口中字符'A'出现的次数
                cnt[1]表示滑动窗口中字符'B'出现的次数
                ...
                以此类推
            */
            int[] cnt = new int[26];
            int length = cs.length;
            //遍历过程中的窗口为[left, right]
            for (int left = 0, right = 0; right < length; right++) {
        
                int cur = cs[right] - 'A';
                //字符 cs[right] 进入窗口，更新 cnt
                cnt[cur]++;
                /*
                    (1) 对于窗口 [left, right] 中的字符串，如果可以选择其中任一字符，并将其更改为任何其他大写英
                    	文字符（该操作最多可执行 k 次），最终使得 [left, right] 中的所有字符都相等，那么必有
                    	sum(所有字符的出现次数) - max(出现次数最多的字符的出现次数）= other(其他字符的出现次数) <= k
                    (2) 所以函数 check(cnt, k) 的功能就是对此进行判断，如果返回值为 false，则说明不能替换成全部相
                        等的字符，需要缩小窗口，直到满足要求为止；如果返回值为 true，则更新 res
                */
                while (!check(cnt, k)) {
        
                    int del = cs[left] - 'A';
                    cnt[del]--;
                    left++;
                }
                //更新 res
                res = Math.max(res, right - left + 1);
            }
            return res;
        }
        
        public boolean check(int[] cnt, int k) {
        
            int max = 0;
            int sum = 0;
            for (int i = 0; i < 26; i++) {
        
                max = Math.max(max, cnt[i]);
                sum += cnt[i];
            }
            return sum - max <= k;
        }
    }

[LeetCode]: https://leetcode.cn/problems/longest-repeating-character-replacement/solution/ping-ping-wu-qi-shuang-zhi-zhen-da-bai-h-fgif/