Python O(n) solution, 164ms


  • 2
    C

    Two steps:

    1. Find the first minimum window that covers all letters in T, with start and end points to the starting and ending point of the minimum window;

    2. Discard the letter x at start and advance to the next letter if it's in T, advance end until it points to the same discarded letter x

    Note: during step 1 and 2, advancing pointers may come to letters that are in T, use hash table extra to keep track of these letters. When the discarded letter is in extra, a window is found without advancing the end pointer.

    String S is only traversed once, so the time complexity is O(n), two hash tables to_find and extra have space O(m).

    def minWindow(self, S, T):
        letters = set(T)
        ls = len(S)
        
        # find the first substring that works
        first_match = self.first_match(S, T)
        if not first_match:
            return ''
        else:
            start, end, extra = first_match
            min_window = (end - start, start, end)
        
        # traverse the string and update start and end
        while start < end < ls:
            discard = S[start]
            
            # move start on to the next letter
            while start < end:
                start += 1
                if S[start] in letters:
                    break
            
            # if discarded letter has extra, no need update end    
            if discard in extra:
                extra[discard] -= 1
                if extra[discard] == 0:
                    extra.pop(discard)
                min_window = min(min_window, (end - start, start, end))
                continue
            
            # otherwise move end until it points to the discarded letter
            while end < ls:
                end += 1
                if end == ls:
                    continue
                
                letter = S[end]
                if letter == discard:
                    min_window = min(min_window, (end - start, start, end))
                    break
                
                if letter in letters:
                    extra[letter] += 1
    
        _, start, end = min_window
        return S[start: end + 1]
        
    def first_match(self, S, T):
        letters = set(T)
        to_find = collections.defaultdict(lambda: 0)
        extra = collections.defaultdict(lambda: 0)
        
        # build hash table
        for i in T:
            to_find[i] += 1
        
        # find the start position
        for index, letter in enumerate(S):
            if letter in to_find:
                start = index
                break
        else:
            return False
            
        # find the end position
        for index, letter in enumerate(S[start:], start):
            if letter not in letters:
                continue
            if letter in to_find:
                to_find[letter] -= 1
                if to_find[letter] == 0:
                    to_find.pop(letter)
            else:
                extra[letter] += 1
            if not to_find:
                end = index
                break
        else:
            return False
        return start, end, extra

Log in to reply
 

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