[76. Minimum Window Substring] #leetcode

76_1014.py

class Solution(object):
  # O(n) O(n)
    def minWindow(self, s, t):
        # get counts of each character and length of t
        need, missing = collections.Counter(t), len(t)
        
        # initialize indice
        i = I = J = 0
        
        # loop s 
        for j, c in enumerate(s, 1):
            # make sure only needed is reduced
            missing -= need[c] > 0
            # minus the count for every char
            need[c] -= 1
        
            if not missing:
                # missing is zero 
                # left move to one of needed chars
                while i < j and need[s[i]] < 0:
                    need[s[i]] += 1
                    i += 1
                # find min length
                if not J or j - i <= J - I:
                    I, J = i, j
        # return result
        return s[I:J]