侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 674 篇文章
  • 累计创建 128 个标签
  • 累计收到 20 条评论

目 录CONTENT

文章目录

【滑动窗口】替换后的最长重复字符

GabrielxD
2022-10-18 / 0 评论 / 0 点赞 / 158 阅读 / 382 字
温馨提示:
本文最后更新于 2022-11-04,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

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


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

解题

方法一:滑动窗口

思路

滑动窗口模板题。
维护一个 maxCnt 用来标识滑动窗口中出现次数最多的字符出现的次数,maxCnt + k 小于窗口的大小时(即在窗口内替换 k 个字符不够时)收缩窗口。

代码

class Solution {
    static final int HASH_LEN = 'Z' + 1;

    public int characterReplacement(String s, int k) {
        int[] window = new int[HASH_LEN];
        char[] chs = s.toCharArray();
        int n = chs.length;
        int left = 0, right = 0;
        int maxCnt = 0, maxLen = 0;
        while (right < n) {
            maxCnt = Math.max(maxCnt, ++window[chs[right++]]);
            while (right - left > maxCnt + k) {
                maxCnt = Math.max(maxCnt, --window[chs[left++]]);
            }
            maxLen = Math.max(maxLen, right - left);
        }
        return maxLen;
    }
}
0

评论区