Fast python solution, 112ms, 21 lines


  • 1
    C

    Best runtime is 112ms (beats 100% of python submissions)




    idea:

    go through the string, record the positions of the characters we want to find. Whenever we find all the characters, keep updating the start position to find a substring with local minimum length. After this, update the start position to next one and then keep looking for the missing character.

    Implentation:

    use a dictionary d to store the number of each character we need to find. (negative values mean we have some extra!) ToFind is the total number of characters we still need to find. ind is a list of indices of the characters in d. head is a pointer in ind so ind[head] is the start position of the substring and s[ind[head]] is that character).



    Nore: I use a small trick to initialize L, and R, the start and end position of the minimum window substring. (Their initial values have properties that R - L = len(s) and s[L:R+1]="" . Therefore, when we find the first window with indices p and q , q - p must be smaller than R - L so we can update L and R. if we cannot find any window to update L and R, it would return an empty string. )

    def minWindow(self, s, t):
        d = {}
        for c in t:
            d[c] = d.get(c,0) + 1
            
        ToFind, ind = len(t), []
        L, R, head = -len(s)-1, -1, 0
        
        for i, c in enumerate(s):
            if c in d:
                ind.append(i)
                d[c] -= 1
                if d[c] >=0:
                    ToFind -= 1
                if ToFind == 0:
                    while d[s[ind[head]]] < 0: # s[ind[head]] is the character
                        d[s[ind[head]]] += 1
                        head += 1
                    if i - ind[head] < R - L:
                        L, R = ind[head], i
                        
                    d[s[ind[head]]] += 1
                    ToFind += 1
                    head += 1
                    
        return s[L:R+1]

  • 0
    Z

    I love your solution, a two-pointer method + statistics in the middle.

    Thank you for sharing


Log in to reply
 

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