LeetCode 424. 替换后的最长重复字符（滑动窗口）
LeetCode 424. 替换后的最长重复字符（滑动窗口）
Michael阿明
发布于 2020-07-13 14:37:17
发布于 2020-07-13 14:37:17
1. 题目
给你一个仅由大写英文字母组成的字符串，你可以将任意位置上的字符替换成另外的字符，总共可最多替换 k 次。 在执行上述操作后，找到只包含重复字母的最长子串的长度。
注意: 字符串长度 和 k 不会超过 104。
示例 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<int> 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<int> 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
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2020-05-19 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录