题目来源
给一个字符串和一个整数k，可以变化k个字符，使得字符串中连续重复的字符数最多。
我想着一个移动窗口，里面字符个数减去频次最高的字符个数等于k，然后从前往后移动，计算窗口最大的时候窗口内元素个数即为所求。
代码如下：
class Solution {
public:
int characterReplacement(string s, int k) {
int n = s.size();
if (n <= k + 1)
return n;
vector<int> chaNum(26, 0);
int longest = k;
int l = 0, r = k;
for (int i=0; i<=k; i++)
chaNum[s[i]-'A']++;
while (r < n) {
int most = 0;
for (int i=0; i<26; i++)
most = max(most, chaNum[i]);
if (r - l + 1 - most <= k) {
longest = max(longest, r-l+1);
r++;
chaNum[s[r]-'A']++;
}
else {
chaNum[s[l]-'A']--;
l++;
}
}
return longest;
}
};
稍作修改，看着简洁一些。
class Solution {
public:
int characterReplacement(string s, int k) {
int n = s.size();
if (n <= k + 1)
return n;
vector<int> chaNum(26, 0);
int longest = k + 1;
int l = 0, r = 0;
while (r < n) {
chaNum[s[r]-'A']++;
int most = *max_element(chaNum.begin(), chaNum.end());
while (r - l + 1 - most > k)
chaNum[s[l++]-'A']--;
longest = max(longest, r-l+1);
r++;
}
return longest;
}
};
