題目來源
給一個字符串和一個整數(shù)k，可以變化k個字符描滔，使得字符串中連續(xù)重復(fù)的字符數(shù)最多重抖。
我想著一個移動窗口圆存，里面字符個數(shù)減去頻次最高的字符個數(shù)等于k，然后從前往后移動仇哆，計(jì)算窗口最大的時候窗口內(nèi)元素個數(shù)即為所求沦辙。
代碼如下：
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;
}
};
