Idea:

Step 1. Just welcome the new comer.

Step 2. Relocation the starting point trying to make the window a largest and valid expanded window.

Step 3. Update the answer

```
class Solution(object):
def characterReplacement(self, s, k):
"""
:type s: str
:type k: int
:rtype: int
"""
window, strt, charcnt, ans = [], 0, {}, 0
for i in xrange(len(s)):
#Step 1
tmp = None
if s[i] in charcnt:
tmp = charcnt[s[i]]
tmp[0] -= 1
else:
tmp = [-1, s[i]]
charcnt[s[i]] = tmp
heapq.heappush(window, tmp)
#Step 2
while (i - strt + 1) + (heapq.nsmallest(1, window))[0][0] > k:
charcnt[s[strt]][0] += 1
strt += 1
#Step 3
ans = max(ans, 1 + i - strt)
return ans
```