Python O(n) Iterative solution

  • 0

    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):
        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)
            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
            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.