Leetcode 76: Minimum Window Substring

 

Code

import sys
from collections import defaultdict

class Solution(object):
    def minWindow(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: str
        """
        mapping = defaultdict(int)
        for ch in t:
            mapping[ch] = mapping[ch] + 1
            
        d = sys.maxint
        valid = len(t)
        start = 0
        minstart, minend = None, None

        for end, ch in enumerate(s):
            if mapping[ch] > 0:
                valid -=1 
            mapping[ch] -= 1

            while valid == 0:
                if end - start + 1 < d:
                    minend, minstart = end, start
                    d = end - start + 1

                mapping[s[start]] += 1
                if mapping[s[start]] > 0:
                    valid += 1
                start += 1 
        
        if minstart is None:
            return ""
        else:
            return s[minstart:minend+1]
        
        

 

Idea

Create a dictionary mapping which stores how many times each character in t should appear. (line 11-13)

You have two pointers, start and end, which denote the border of the temporary window you are looking at. valid is a variable that when it reaches 0, we know the current window contains all characters in t. At first, `start` pointer is at index 0 and `end` pointer starts to move right.

When valid reaches 0,  you start to maintain the minimum string: you have variables d, minend and minstart and do the maintenance in line 26-28.

Then, you start to check whether a smaller window can also contains t. To do so, you move start pointer left. At the same time, you need to recover mapping dictionary.

 

Reference:

https://discuss.leetcode.com/topic/30941/here-is-a-10-line-template-that-can-solve-most-substring-problems