这道题很显然是滑动窗口题，通过替换相同字符来求的可以包含相同字母的最长字符串的长度有些许难度。
写完这道题后才又对通过表的形式处理数据有更好的理解。
题目
力扣：424. 替换后的最长重复字符
给你一个字符串 s 和一个整数 k 。你可以选择字符串中的任一字符，并将其更改为任何其他大写英文字符。该操作最多可执行 k 次。
在执行上述操作后，返回 包含相同字母的最长子字符串的长度。
题解
求解此题的关键在于满足窗口该区间除了出现次数最多的那个字符之外，剩余的字符数量不超过 k 个。
然后就是如何获得出现次数最多的字符，显然需要维护一个字符表对该表求最大值，使用 C++ STL 中哈希表的核心实现 <unordered_map> 是不错的选择。
我先尝试索引一个不存在的键，假若其类型为：unordered_map<char, int>返回的是 0 那就好办了。对于添置新字符只需要对其索引自增就好了。
1
2
|
std::unordered_map<char, int> count;
std::cout << count['a']; // output: 0
|
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
|
class Solution
{
public:
int characterReplacement(std::string s, int k)
{
std::unordered_map<char, int> count; // 哈希表统计窗口频率
int left = 0, maxLength = 0, maxCount = 0, winLength, right;
// 滑动窗口从左到右移动，left/right 定义当前子串
for (right = 0; right < s.length(); right++)
{
count[s[right]]++; // count[字符] 记录出现次数
// 维护 maxCount，记录窗口内出现最多的字符次数
// maxCount 只增不减
maxCount = std::max(maxCount, count[s[right]]);
winLength = right - left + 1;
// 判断合法性，窗口长度 - maxCount <= k
// 否则左指针收缩
if (winLength - maxCount > k)
{
count[s[left]]--;
left++;
}
maxLength = std::max(maxLength, right - left + 1);
}
return maxLength;
}
};
|
比较特殊的就是得到 maxCount 的式子：
1
|
maxCount = std::max(maxCount, count[s[right]]);
|
不需要去求得哈希表内的最大值，只需要获得新添到窗口内字符的最大值就好了。其只在扩张窗口的时候更新频次，在此时只有 s[right] 的计数可能会变大，只需要求其的数字进行最大值比较就好了。
maxCount 记录是某个 right 位置下能达到的最大长度，这会影响到下面窗口的当 maxCount 过期导致少收缩，此时窗口最大长度只能保持之前获得 maxCount 的长度大小。尽管窗口晚收缩，但最终当又有新的符合 maxLength 值出现才会更新 maxLength，当前窗口长度仅被限制在了 maxLength 内，不会导致最终结果偏大。