An easy understanding python O(2n) solution use two Counters with comments


  • 0
    T
    class Solution:
    # @return a string
    def minWindow(self, s, t):
        window = collections.Counter(t)  # if window is empty, we find a window
        extra = {char: 0 for char in t}  # use extra to check char if in t and count extra letters in window
        i, start, end = 0, 0, len(s)+1  # window size is end-start, if end == len(s)+1, there is no window in s
        for j, char in enumerate(s):
            if char in extra:
                if char in window:
                    window[char] -= 1  # we find a char in window
                    if window[char] == 0:  # we find all this char in window
                        del window[char]
                else:
                    extra[char] += 1   # we find extra char in this window
                while not window:  # we find a window
                    char = s[i]  # scan from i
                    i += 1
                    if char not in extra:
                        continue  # char not in this window, window size can be smaller
                    elif extra[char]:  # extra[char] > 0
                        extra[char] -= 1  # window size can be smaller
                    elif not extra[char]:  # extra[char] == 0 the window can't be smaller
                        window[char] += 1  # we restart to find a new window
                        if j - i + 2 < end - start: # this window size is j+1 - (i-1)
                            start, end = i-1, j+1
        return '' if end == len(s)+1 else s[start:end]

Log in to reply
 

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