0076._Minimum_Window_Substring.md

76. Minimum Window Substring

难度: Hard

刷题内容

原题连接

• https://leetcode.com/problems/minimum-window-substring/description/

内容描述

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).

Example:

Input: S = "ADOBECODEBANC", T = "ABC"
Output: "BANC"
Note:

If there is no such window in S that covers all characters in T, return the empty string "".
If there is such window, you are guaranteed that there will always be only one unique minimum window in S.

解题方案

思路 1

• 首先搞几个corner case
• 开始步入正题，我们脑子里面必须要有一个window的概念，只要这个window的end小于len(s)，就一直搞下去
• 记录一下t中字符和其频率，然后随着end的变大不停更新这个maps，即出现一个字符，如果该字符在maps里面，我们就对应的自减一下这个字符在maps中的频率
• 用一个counter记录这个maps里面频率不为0的字符个数，即key个数，当counter为0的时候我们就知道t中所以的字符都在我们的window里面了
• 这个时候，我们就可以开始自增begin了，然后只要仍然可以保持counter为0（即所有字符都还在window里面），我们就一直移动begin以减小window的size
• 当最后while end < len(s)循环出来的时候，我们判断一下我们的window的length是不是变化了（最开始设置了inf最大值），如果变化了说明我们找到了符合要求的window，否则没有

class Solution(object):
    def minWindow(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: str
        """
        if len(t) > len(s):
            return ''
        if s == '' or t == '':
            return ''
        maps = collections.Counter(t)
        counter = len(maps.keys())
        begin, end, head, length = 0, 0, 0, float('inf')
        while end < len(s):
            if s[end] in maps:
                maps[s[end]] -= 1
                if maps[s[end]] == 0:
                    counter -= 1
            end += 1
            while counter == 0:
                if s[begin] in maps:
                    maps[s[begin]] += 1
                    if maps[s[begin]] > 0:
                        counter += 1
                    if end - begin < length:
                        length = end - begin
                        head = begin
                begin += 1
        if length == float('inf'):
            return ''
        return s[head:head+length]