文章
问答
冒泡
LeetCode 每日一题

替换后的最长重复字符

image.png

思路

双指针
通过双指针维护一个滑动窗口,通过对右指针-左指针算出窗口大小,判断条件为窗口大小减去重复字符出现的最大次数与可替换次数k进行比较,如果大于k次之后则需要进行左指针右移,重复以上步骤。
题目中特殊条件“仅为大写英文字母”,那么可以通过维护一个26位的数组来对出现次数进行维护,然后存放到变量中进行比较得出字符重复出现的最大次数。

class Solution{
    public int charReplacement(String s, int k){
        int[] chars = new int[26]; // 通过26位的数组维护滑动窗口中每个字符出现的次数
        int left=0,right=0; //左右指针
        int n=s.length();
        int maxn = 0; // 重复字符出现的最大次数
        while(right<n){
            chars[s.charAt(right)-'A']++; //计数
            maxn = Math.max(maxn, chars[s.charAt(right)-'A']);//遍历过程中维护重复字符出现的最大次数;
            if(right-left+1-maxn>k){
                chars[s.charAt(left)-'A']--;//左指针右移,需要将之前的左指针对应的字符计数减一
                left++;
            }
            right++;
        }
        return  right-left;
    }
}
数据结构与算法

关于作者

Kirago
个人站点 https://kiragoo.github.io/
获得点赞
文章被阅读