# Minimum Window Substring

<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).
>
> For example,\
> **S**=`"ADOBECODEBANC"`\
> **T**=`"ABC"`
>
> Minimum window is`"BANC"`.
>
> **Note:**\
> If there is no such window in S that covers all characters in T, return the empty string`""`.
>
> If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.

## Thoughts

问数组内满足条件的子数组的最小size，标准动态滑动窗口问题。r照例不断往前移动, 但在没找到permutation前, l都维持不动. 当permutation找到后, 把l不断往前移动到permutation开始的地方, 即略过那些不在permutation中的元素. 这时看新窗口的长度是多少, 如果是最小则存下来. 然后再让l往前一格, 重新寻找以新l为开头的包含permutation的r能在哪. 重复此过程.

统计几样元素的个数是否够，用freq map。先根据个数置为相应的负数，代表欠缺这些。当==0意味着对应元素个数满足。配合另一个计数cursize记录当前满足条件的总个数，遍历到i且freq\[i] <= 0时++cursize, 表面找到一个顶用的；当移出i且freq\[i] == 0时，意味着移出会让顶用的少一个, --cur\_size; cur\_size == t.size()意味着当前块满足所需。

## Code

```cpp
/*
 * @lc app=leetcode id=76 lang=cpp
 *
 * [76] Minimum Window Substring
 */
class Solution {
public:
    string minWindow(string s, string t) {
        int l = 0, r = 0, min_len = s.size(), cur_size = 0;
        string res = "";
        unordered_map<char, int> freq;
        for (char c : t) {
            if (!freq.count(c)) freq[c] = 0;
            --freq[c];
        }
        while (r < s.size()) {
            const auto cr = s[r];
            if (!freq.count(cr)) freq[cr] = 0;
            ++freq[cr];
            if (freq[cr] <= 0) {
                ++cur_size;
            }
            while (cur_size == t.size()) {
                const auto cl = s[l];
                if (r - l + 1 <= min_len) {
                    min_len = r - l + 1;
                    res = s.substr(l, min_len);
                }
                if (freq[cl] == 0) {
                    --cur_size;
                }
                --freq[cl];
                ++l;
            }
            ++r;
        }
        return res; 
    }
};


```

## Analysis

时间复杂度O(s.len), l和r最多走这么多. 空间O(1).