Longest Repeating Character Replacement

Mar 05, 2019

emmmm，这道题一开始的解法虽然AC了，但是时间复杂度是O(n^2)，但是最佳解法却是O(n)，先看下我的解法：

class Solution {
public:
int characterReplacement(string s, int k) {
int len = s.size();
int res = 0;
int j, a;
for(int i = 0; i < len; i++) {
char c = s[i];
a = k;
for(j = i+1;j < len; j++) {
if (c != s[j]) {
if (a == 0) break;
else a--;
}
}
res = max(j-i, res);
}

for(int i = 0;i < k && i+1 < len; i++) {
char c = s[i+1];
a = k-i-1;
for(j = i + 2;j < len; j++) {
if (c != s[j]) {
if (a == 0) break;
else a--;
}
}
res = max(j-i, res);
}

return res;
}
};


OK，现在可以忽略掉上面的解法了，看看O(n)的解法是怎样的：

class Solution {
public:
int characterReplacement(string s, int k) {
vector<int> ch(26);
int start = 0, end = 0, max_count = 0;
int len = s.size();
while(end < len) {
ch[s[end] - 'A']++;
// update max_count
max_count = max(max_count, ch[s[end]-'A']);
end++;
if ( end - start > max_count + k) {
ch[s[start] - 'A']--;
start++;
}
}
return end - start;
}
};


LeetCodeLeetCode

Sum Root to Leaf Numbers

Minimum Falling Path Sum