2018-06-29 22:56:24
问题描述：
问题求解：
本题是一条字符串问题，且是求Optimal，自然最初想到的是使用DP来进行求解，但是问题就是如果采用DP的话，前一个状态也太多了，和替换了多少了k值相关，因此从这个角度来说，使用DP来处理本题是不太合适的。
那么，另一个处理的手段滑动窗口就呼之欲出了。
在本题中窗口[start, end]来维护，其中只要窗口长度 - 窗口中出现字符最多的个数 <= k则当前窗口的长度符合题意，只要找出最长的符合条件的窗口即可。
问题是如果出现了上述条件不满足的情况，那么就需要减小窗口大小使之满足条件。
这里有一个trick，就是在减小窗口大小的时候是不需要对maxcnt的大小进行修改的，因为如果要得到一个比当前的res更好的解，那么势必窗口大小要增大，同时maxcnt也要增大。因此这里不需要重新遍历一遍来获得新的窗口中的maxcnt。
public int characterReplacement(String s, int k) {
int res = 0;
int start = 0;
int[] cnt = new int[26];
int maxcnt = 0;
for (int end = 0; end < s.length(); end++) {
maxcnt = Math.max(maxcnt, ++cnt[s.charAt(end) - 'A']);
if (end - start + 1 - maxcnt > k) {
cnt[s.charAt(start++) - 'A']--;
}
res = Math.max(res, end - start + 1);
}
return res;
}