Minimum Window Substring

题目描述

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

For example,

S = "ADOBECODEBANC"
T = "ABC"

Minimum window is "BANC".

• sliding window maximum

解题方法

类似longest substring类型的题目，这种题目的code结构我应该记下来，类似的题目都可以用 这种模板来解。

Solution

class Solution(object):
    def minWindow(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: str
        """
        if not s or not t:
            return ""

        tMap = {}
        for c in t:
            if c in tMap:
                tMap[c] += 1
            else:
                tMap[c] = 1

        left = 0
        right = 0
        numT = len(tMap.keys())
        minLen = sys.maxint
        result = ""

        for left in range(len(s)):
            while left <= right and right < len(s) and numT > 0:
                if s[right] in tMap:
                    tMap[s[right]] -= 1
                    if tMap[s[right]] == 0:
                        numT -= 1
                right += 1 # don't forget

            if numT == 0:
                curLen = right - left # be carefult of the bound
                if curLen < minLen:
                    minLen = curLen 
                    result = s[left: right]
            if s[left] in tMap:
                tMap[s[left]] += 1
                if tMap[s[left]] == 1:
                    numT += 1

        return result

Reference