本文共 1608 字，大约阅读时间需要 5 分钟。

1. 题目

给你一个仅由大写英文字母组成的字符串，你可以将任意位置上的字符替换成另外的字符，总共可最多替换 k 次。

注意:

示例 1:输入:s = "ABAB", k = 2输出:4解释:用两个'A'替换为两个'B',反之亦然。示例 2:输入:s = "AABABBA", k = 1输出:4解释:将中间的一个'A'替换为'B',字符串变为 "AABBBBA"。子串 "BBBB" 有最长重复字母, 答案为 4。

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/longest-repeating-character-replacement

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

类似题目：

• [i,j]区间内最多的数量的字符保留，其余的"替换掉"
• 右端点每次都向右移动1步，左端点只在不满足的情况下右移1步
• 因为只关心最大长度，所以左端点不必移动到区间满足题意，因为那样的区间不是最长的

class Solution {
   public:    int characterReplacement(string s, int k) {
           if(k >= s.size())        	return s.size();        int i = 0, j = 0, ans = 0;        vector
   
     count(26,0);        while(j < k)        	count[s[j++]-'A']++;        while(j < s.size())        {
           	count[s[j++]-'A']++;        	if(j-i-*max_element(count.begin(),count.end()) <= k)//需要替换的个数        		ans = max(ans, j-i);        	else        		count[s[i++]-'A']--;        }        return ans;    }};
   

60 ms 7.2 MB

• 优化下，*max_element，每次要找26个int，效率不高

class Solution {
   public:    int characterReplacement(string s, int k) {
           if(k >= s.size())        	return s.size();        int i = 0, j = 0, idx, maxc = 0, ans = 0;        vector
   
     count(26,0);        while(j < s.size())        {
               idx = s[j++]-'A';        	count[idx]++;            if(maxc < count[idx])            //只有新加入的字符的个数大于历史重复字符最高数时，才能更新答案                maxc = count[idx];        	if(j-i-maxc <= k)//需要替换的个数        		ans = max(ans, j-i);        	else        		count[s[i++]-'A']--;        }        return ans;    }};
   

4 ms 7.3 MB

转载地址：https://michael.blog.csdn.net/article/details/106213574 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！