# Three sliding window solutions with clear and detailed explain.

• Solution 1:

``````#In this window, delete all 'one letter(For making this window is as long as possible,this letter must be the most frequent in this window.)',
# and the letters left <=k,and this window is effective.
#If not, the start of window moves right until the window is effective again.
def characterReplacement(self, s, k):
hash=[0 for i in range(26)]
st,en,res=0,0,0
while en<len(s):
hash[ord(s[en])-ord('A')]+=1
while en-st-max(hash)+1>k:hash[ord(s[st])-ord('A')]-=1;st+=1
if res<en-st+1:res=en-st+1
en+=1
return res
#Runtime:272ms(beats 47.94% python submissions)
``````

Solution 2:

``````def characterReplacement(self, s, k):
if k>=len(s)-1:return len(s)
hash={}
#For sliding distance, I only need to consider about the position of each continuous same letter, so I create a hash to sign this.
for i in range(len(s)):
if i>0 and s[i]==s[i-1]:hash[s[i]][-1][1]=i
elif hash.has_key(s[i]):hash[s[i]].append([i,i])
else:hash[s[i]]=[[i,i]]
m=0
for (key,value) in hash.items():#Same process for each letter,
st,en,kt=0,0,k
while en<len(value):
if en==len(value)-1 or kt<value[en+1][0]-value[en][1]-1:
if kt+value[en][1]-value[st][0]+1>m:m=kt+value[en][1]-value[st][0]+1
if en==len(value)-1:break
if st<en:kt+=value[st+1][0]-value[st][1]-1
else:en+=1
st+=1
else:
kt-=value[en+1][0]-value[en][1]-1
en+=1
return m if m<len(s) else len(s)
#Runtime:215ms(beats 57.65% python submissions)
``````

Solution 3:refer to @StefanPochmann

``````#Promoted from the first solution:
#Each time, the end of the window moves right,by one step,
#but only if the window is ineffective("en-st-max(hash)+1>k"), than need to move the start right,by one step.
#As can be seen, the length of window is always increated, and always effective.
#At last, the length of the window is the result.
def characterReplacement(self, s, k):
hash=[0 for i in range(26)]
st,en=0,0
while en<len(s):
hash[ord(s[en])-ord('A')]+=1
if en-st-max(hash)+1>k:hash[ord(s[st])-ord('A')]-=1;st+=1
en+=1
return en-st
#Runtime:209ms(beats 60.2% python submissions)
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.