首先提出一个子问题: 长度位$n$的字符串,若将该字符串全部修改为统一的字符,则最少需要修改多少个字符?
我们只需统计出当前字符串出现的最多的字符有多少个即可。 设为$x$
则最少需要修改的字符个数便为:$n - x$。
再回到这个问题上,设指针left = 0
和 right = 0
我们只需从前往后扫描,每次right++
,如果当前right
指向的字符使得区间$[left, right]$要修改的字符
个数大于$k$了。则left ++
。直到新的区间满足要修改的字符个数小于等于$k$,此时更新答案。
举个栗子: k = 2
idx 0 1 2 3 4 5 6
a b b a a a
当6
的位置是a
的时候:
idx 0 1 2 3 4 5 6
a b b a a a a
此时区间$[0, 6]$满足最多修改$2$个
当6
的位置是b
的时候:
idx 0 1 2 3 4 5 6
a b b a a a b
此时区间$[0, 6]$需要修改$3$个
left
从0
指向1
, 但是$[1, 6]$仍然需要$3$个, left
指向2
此时最多修改2个即可满足。
最不济的情况就是left
指向right - 2
,长度为3,最多修改2
个
class Solution {
public:
int characterReplacement(string s, int k) {
int left = 0, right = 0; // 两个指针
int res = 0;
int Max = -1; // 当前区间出现最多的字符数
vector<int > nums(26); // 用来统计字符出现的个数
int n = s.size();
while(right < n){
// 每次去更新字符出现的最大数
char c = s[right];
nums[c - 'A'] ++ ;
Max = max(Max, nums[c - 'A']);
// 判断区间是否满足条件 注意这里当left++的时候,要提前更新Max,在left++
while(right - left + 1 - Max > k){
nums[s[left] - 'A'] --;
Max = max(Max, nums[s[left] - 'A']);
left ++;
}
// 此时的 [left, right]的区间一定是满足条件的,更新答案即可。
res = max(res, right - left + 1);
right ++;
}
return res;
}
};
懒得再开一篇就在你这注释啦 若烦删
更正:
Most_character_number
这么长的名字改成maxCount
更省键盘让俺好好拜读一下大佬的代码 hhh
①纯萌新②这是你的代码逻辑,我只是(在你注释基础上)又注释一下
这个不是y总说的那个玄学的题解吗?
真的嘛哈哈哈,有意思,在哪个视频里说的呀
同问~