以最左边为开始，往右遍历，不一样的个数大于K的时候停止，回到第一个不一样的地方，以它为开始，继续。。
用QUEUE记录每次不一样的INDEX,以便下一个遍历开始，
从左往右，从右往左各来一次。。加上各种剪枝情况，比如未遍历的数量<剩余K的数量，比如已经记录过某个INDEX了。。
然后TLE了。。。最后放TLE的方法。。不知道有什么意义。。
上面的做法是左右各来一次，那是否可以使用滑窗呢。。
然后没做出来。。看了讨论区。。果然是滑窗。。
思路：
统计当前滑窗内最多的字母，窗口宽度 - 最多字母数量 <= K，就可以继续尝试扩大窗口，R++。 否则缩小，L++。
比我一开始的那个傻逼办法的改进在于，自动转换字母，我那个必须记录不同字母，比如AAABBBBB当B多的时候，必须退回到第一个B，重新遍历。。而且不用反向再来一次。
至少。。我。。猜对。。滑。。滑窗。。了。。
public class Solution
{
public int characterReplacement(String s, int k)
{
int[] letter = new int[26];
int l = 0;
int most = ++letter[s.charAt(0) - 'A'];
int res = 1;
for(int r = 1; r < s.length();r++)
{
most = Math.max(most,++letter[s.charAt(r) - 'A']);
if(most + k < r - l + 1) // can't maintain this size of window
{
letter[s.charAt(l++)-'A']--;
}
res = Math.max(res,r-l+1);
}
return res;
}
}
二刷。
这个题刚做的，还有印象，滑窗。
但是凭印象做完，回头看这个做法非常巧妙。
我还记得一开始的思路是滑窗，但是做不出来，当时的想法是：
最多的字母 + Others(k) = Length
每次滑窗扩大都需要统计最多的字母，然后相应地要改变Others（或者不改变），再和K比较，决定窗口的左端是否缩进，然后缩进又会减少相应的字母，又要重新判断最多的字母。。。此时右端保持不动。。。
这里忽略了一个问题就是，缩进的目的有2个，一个是通过减少不一样的字母(others)来满足others <= k；或者通过改变最多的字母(most)来满足others <= k，因为只有在满足的情况下我们才会更新res的最大值。 简而言之，通过不停地让窗口左端缩进，目的只有一个others <= k，一旦这个满足我们就可以update res，但是，既然我们都他妈缩进了，肯定比前面的结果小，还更新个鸡巴。。
这里巧妙就巧妙在，左边缩进的同时右边扩大，因为窗口再变小即使满足others <= k，窗口大小也是小于res的，so why bother...and who gives a shit..所以直接右边扩大就行了。。
一开始的想法是尽量满足others <= k的时候判断窗口大小；
后来的做法是保持窗口>当前最大值res的情况下，我们才看是否满足others <= k，满足才更新。。
这些问题一刷都没想，光觉得卧槽这个做法牛逼啊。
其实二刷仔细想想，才发现，确实牛逼啊
public class Solution {
public int characterReplacement(String s, int k) {
if (s.length() == 0) return 0;
int[] map = new int[26];
int most = ++map[s.charAt(0) - 'A'];
int res = 1;
int left = 0;
for (int right = 1; right < s.length(); right++) {
most = Math.max(most,++map[s.charAt(right) - 'A']);
if (right - left + 1 > most + k) {
map[s.charAt(left++) - 'A']--;
} else {
res = Math.max(res,right - left + 1);
}
}
return res;
}
}
三刷。
脑残啊卧槽，又忘了怎么做了。
windowSize - numOfMajorityElement <= K
主要就是这行，满足的时候更新windowSize，
不满足的时候减少windowSize，减少之后numOfMajorityElement也会变，但是不会变大。
public class Solution {
public int characterReplacement(String s, int k) {
if (s.length() == 0) return 0;
int res = 0;
int l = 0;
int[] letters = new int[26];
int maj = 0;
for (int r = 0; r < s.length(); r++) {
char c = s.charAt(r);
maj = Math.max(maj, ++ letters[c -'A']);
int winSize = r - l + 1;
if (winSize - maj <= k) {
res = Math.max(winSize, res);
} else {
letters[s.charAt(l++) - 'A'] --;
}
}
return res;
}
}