看数据范围,是滑动窗口问题。
1. 每次i移动一个
2. j根据情况移动一个(在出现无法满足的情况下移动)
3. 计算中间结果,再计算最后结果
C++ 代码
class Solution {
public:
int characterReplacement(string s, int k) {
unordered_map<char, int> cnt;
int res = 0;
for(int i=0, j=0; i<s.size(); ++i) {
cnt[s[i]]++;
int max_cnt = 0;
for(auto iter : cnt) max_cnt = max(max_cnt, iter.second);
if(i-j+1-max_cnt > k) {
cnt[s[j]]--;
j++;
}
res = max(res, i-j+1);
}
return res;
}
};