LeetCode每日一题-9：替换后的最长重复字符串-阿里云开发者社区

LeetCode每日一题-9：替换后的最长重复字符串

2023-01-05 104

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： LeetCode每日一题-9：替换后的最长重复字符串

题目描述：

给你一个仅由大写英文字母组成的字符串，你可以将任意位置上的字符替换成另外的字符，总共可最多替换 k 次。在执行上述操作后，找到包含重复字母的最长子串的长度。

注意：字符串长度和 k 不会超过 10^4。

示例 1：

输入：s = "ABAB", k = 2

输出：4

解释：用两个'A'替换为两个'B',反之亦然。

示例 2：

输入：s = "AABABBA", k = 1

输出：4

解释：

将中间的一个'A'替换为'B',字符串变为 "AABBBBA"。

子串 "BBBB" 有最长重复字母, 答案为 4

思路分析：

一看到最长字符串就想到滑动窗口。

算法流程：

右边界先移动找到一个满足题意的可以替换 k 个字符以后，所有字符都变成一样的当前看来最长的子串，直到右边界纳入一个字符以后，不能满足的时候停下；
然后考虑左边界向右移动，左边界只须要向右移动一格以后，右边界就又可以开始向右移动了，继续尝试找到更长的目标子串；
替换后的最长重复子串就产生在右边界、左边界交替向右移动的过程中。

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        from collections import defaultdict
        d = defaultdict(int)
        l = 0
        maxn = 0
        for r in range(len(s)):
            d[s[r]] += 1
            maxn = max(maxn, d[s[r]])
            if r - l + 1 > maxn + k:  # bc it is for loop, r += 1 is later than if clause
                d[s[l]] -= 1
                l += 1
        return len(s) - l

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,right=0;
        int maxCount=0,res=0;
        int[] freq = new int[26];
        while(right<len){
            freq[chararray[right]-'A']++;
            maxCount=Math.max(maxCount,freq[chararray[right]-'A']);
            right++;
            if(right-left>maxCount+k){
                freq[chararray[left]-'A']--;
                left++;
            }
            res=Math.max(res,right-left);
        }
        return res;
    }
}