当前位置：首页 > article >正文

Leetcode 424-替换后的最长重复字符

article 2025/2/24 22:22:58

给你一个字符串 s 和一个整数 k 。你可以选择字符串中的任一字符，并将其更改为任何其他大写英文字符。该操作最多可执行 k 次。

在执行上述操作后，返回包含相同字母的最长子字符串的长度。
在这里插入图片描述

题解

可以先做LCR 167/Leetcode 03再做本题

滑动窗口（截取字符串）+哈希表（快速获取窗口内每个字符的个数）

本题等价于替换窗口中的K个字符使其变成一个连续子串，我们的目的就是让窗口尽可能扩张，有K个字符的容错机会，容错机会肯定要用给map中出现次数最多的字符才有机会让窗口扩张
–>需要当前窗口中的出现次数最多的字母个数 +K >子串长度，此时当前窗口内的子串满足最长重复子串

算法步骤

一、定义参数：
变量maxOut记录窗口内最多字符的个度
变量res记录最长子字符串的长度
指针left记录滑动窗口的最左边界，初始值为0
指针right遍历数组，记录滑动窗口的最右边界
哈希表map记录窗口内每个字符的个数
chars = s.toCharArray()便于取值

二、遍历数组：
1.指针 right 遍历字符串s ，哈希表中添加chars[right]对应的字符次数
map[chars[right]-‘A’]++
2.进行比较

如果maxOut<map[chars[right]-‘A’],更新maxOut
如果maxOut+k>right-left+1,说明替换窗口中的K个字符可使其变成一个连续子串
(1)利用right-left+1更新res
(2)否则的话，说明此时 k 不够用
把其它不是最多出现的字符替换以后，都不能填满这个滑动的窗口，这个时候须要考虑左边界向右移动
移出滑动窗口的时候，频数数组须要相应地做减法
map[chars[left]-‘A’]–;
left++;

三、返回值：
返回res

class Solution {
    public int characterReplacement(String s, int k) {
        if (s == null) {
            return 0;
        }
        //利用数组代替哈希表，节约空间，本题只包含26个大写字母
        int[] map = new int[26];
        char[] chars = s.toCharArray();
        int left = 0;
        int res = 0;
        int maxCount=0;
        for(int right=0;right<chars.length;right++){
            int index=chars[right]-'A';
            //窗口内s.charAt(right)出现的次数+1
            map[index]++;
            // 在这里维护 maxCount，因为每一次右边界读入一个字符，字符频数增加，才会使得 maxCount 增加
            maxCount = Math.max(maxCount, map[index]);
            // 说明此时 k 不够用
            // 把其它不是最多出现的字符替换以后，都不能填满这个滑动的窗口，这个时候须要考虑左边界向右移动
            // 移出滑动窗口的时候，频数数组须要相应地做减法
            if(maxCount+k < right-left+1){
                map[chars[left]-'A']--;
                left++;
            }else{
                res=Math.max(res,right-left+1);
            }
        }
        return res;
      
    }
}