Python O(n) Iterative solution


  • 0
    A

    Store locations of the elements and a frequency map of characters per index. At each index try to see if removing all the characters occurring less than k times results in a correct substring.

    def longestSubstring(self, s, k):
        
        positions = [ [-1] for _ in range(ord('a'), ord('z')+1) ]
        for i,v in enumerate(s):
            positions[ord(v)-ord('a')].append(i)
        
        def checkCorrect(dic, index):
            i = 0
            zero = 0
            while i<len(dic):
                if dic[i]<k:
                    poss  = positions[i]
                    zero = max(zero,poss[ dic[i] ]+1)
                i+=1
            if zero != 0:
                dic2 = dicCollection[zero-1]
                for i,v in enumerate(dic):
                    if 0<v-dic2[i]<k:
                        return 0
            return index-zero+1
            
        dicCollection = []
        ans = 0
        for i,v in enumerate(s):
            prev = dicCollection[-1][:] if dicCollection else [0]*26
            prev[ ord(v)-ord('a') ] += 1
            dicCollection.append(prev)
            ans = max(ans,checkCorrect( prev,i ))
        return ans

Log in to reply
 

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