76. Minimum Window Substring https://leetcode.com/problems/minimum-window-substring/description/

minimum_window_substring.py

# Time:  O(n)
# Space: O(n)
# 76. Minimum Window Substring
'''
t = "ABC"
s = "ADOBECODEBANC"
d = {"A":1, "B":1, "C":1}
------
d = {"A":1, "B":0, "C":0}
counter = 0
"ADOBECODEBANC"
  i
       j
'''
    
class Solution(object):
    def minWindow(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: str
        """
        d = collections.Counter(t)  # statistic for count of char in t
        
        i, j = 0, 0 # two pointer 
        seats = len(t)  # total # of character to be found in s 
        window = sys.maxint 
        start = 0 

        while j < len(s): # move end to find a valid window
            if s[j] in d and d[s[j]] > 0: # found one match
                seats -= 1
            d[s[j]] -= 1 # might be negative
            j += 1 # move forward
            # when we found a valid window, move i to find a smaller one
            while seats == 0: # found one valid window
                if j - i < window:
                    start = i
                    window = j - i
                d[s[i]] += 1
                # when char exists in t, increase counter
                if d[s[i]] > 0:
                    seats += 1
                i += 1
        # return result
        if window != sys.maxint:
            return s[start: start + window]
        return ""