Three sliding window solutions with clear and detailed explain.


  • 0
    E

    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)
    

Log in to reply
 

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