Question: https://oj.leetcode.com/problems/minimum-window-substring/
Question Name: Minimum Window Substring
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 | class Solution: # @return a string def minWindow(self, S, T): minWindow = [-1,-1] # The begin and end position (both inclusive) of current window begin, end = -1, 0 # The number of each char in current window totalCount = {i:0 for i in T} # Compute the char distribution in T need = {} for item in T: need[item] = need.get(item, 0) + 1 # Find the first window, containing all the characters in T needCount = len(T) while end < len(S): if S[end] in need: if begin == -1: begin = end totalCount[S[end]] += 1 if totalCount[S[end]] <= need[S[end]]: # Find one more char for a qualified window needCount -= 1 # Enough chars to form a window if needCount == 0: break end += 1 else: # Did not find a window return "" # Try to minimize the window length by removing the leftmost items while True: if S[begin] in need: if totalCount[S[begin]] > need[S[begin]]: totalCount[S[begin]] -= 1 begin += 1 else: # Already be minimum break else: begin += 1 minWindow = [begin, end] # Try next window, ending with S[begin] while True: # Find the next window, ending with current S[begin] end += 1 while end < len(S): if S[end] == S[begin]: break if S[end] in totalCount: totalCount[S[end]] += 1 end += 1 else: # No windows left. break # Minimize current window, by removing the leftmost items begin += 1 while begin <= end: if S[begin] in need: if totalCount[S[begin]] > need[S[begin]]: totalCount[S[begin]] -= 1 begin += 1 else: # Minimized break else: begin += 1 if end - begin < minWindow[1] - minWindow[0]: # Find a shorter window minWindow[0], minWindow[1] = begin, end return S[minWindow[0]: minWindow[1]+1] |