###### tags: `Leetcode` `hard` `sliding window` `python` `Top 100 Liked Questions`

# 76. Minimum Window Substring

## [題目連結:] https://leetcode.com/problems/minimum-window-substring/

## 題目:
Given two strings s and t of lengths m and n respectively, return the **minimum window substring** of s such that every character in t (**including duplicates**) is included in the window. If there is no such substring, return the empty string "".

The testcases will be generated such that the answer is **unique**.

A **substring** is a contiguous sequence of characters within the string.

**Follow up: Could you find an algorithm that runs in O(m + n) time?**

**Example 1:**

Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t.

**Example 2:**

Input: s = "a", t = "a"
Output: "a"
Explanation: The entire string s is the minimum window.

**Example 3:**

Input: s = "a", t = "aa"
Output: ""
Explanation: Both 'a's from t must be included in the window.
Since the largest window of s only has one 'a', return empty string.

## 解題想法:
* 要求在s中找出**包含t所有字符**的**最短連續字串**
* 因為要求O(N)時間，往雙指針去想
* **Sliding window** 💪
* 額外需要: 字典存t的字符與其出現的次數
* **Step1:** tail逐一往右遍歷
* **Step2:** curSum紀錄在head~tail區間內包含t中元素的個數
* **Step3:** 當curSum==len(t)表示目前head~tail區間符合題目要求的區間，但不一定是最短區間
* **Step4:** 移動head，檢查是否還有機會縮小區間
* **Step5:** 若curSum!=len(t)，則繼續**Step1**

## Python:

from collections import defaultdict

class Solution(object):
    def minWindow(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: str
        """
        dic=defaultdict(int)
        for val in t:
            dic[val]+=1
        head=0
        tail=0
        minLen=float('inf') #區間長
        res=""
        curSum=0 #當前區間包含t元素的數量
        while tail<len(s):
            dic[s[tail]]-=1
            #若為負，表示不在t中or超過t中該char的數量
            if dic[s[tail]]>=0:
                curSum+=1
            while curSum==len(t):
                #更新長度
                if minLen>(tail-head+1):
                    minLen=tail-head+1
                    res=s[head:tail+1]
                #移動head
                dic[s[head]]+=1
                #大於0代表 刪掉的是t中的元素
                if dic[s[head]]>0:
                    curSum-=1
                head+=1
            tail+=1
        return res
    
if __name__=='__main__':
    result=Solution()
    ans=result.minWindow(s = "ADOBECODEBANC", t = "ABC")
    print(ans)