LeetCode 424 替换后的最长重复字符
🟡 中等 https://leetcode.cn/problems/longest-repeating-character-replacement/description/
特殊的点
max_count 的更新不用每次左移时更新。
while 中的更新 max_count 操作可以省略掉，因为当前找到一个 max_count 后答案就已经更新为 max_count+k ，如果有更大的那么一定时 max_count(新)>max_count(旧) 因此 max_count 应该是递增的，至少不应该减小。 因此 while 中的 for循环可以省略。
class Solution {
public:
int characterReplacement(string s, int k) {
int left = 0;
int max_count = 1;
unordered_map<char, int> hash_map;
int res = 0;
for (int i = 0; i < s.size(); i++) {
hash_map[s[i]]++;
max_count = max(max_count,hash_map[s[i]]);
while (i - left + 1 - max_count > k) {
hash_map[s[left]]--;
//for (const auto& pair : hash_map) {
//
// max_count = max(max_count, pair.second);
//
// }
left++;
}
res = max(res, i - left + 1);
}
return res;
}
};