solution.md

# 最小覆盖子串
<p>给你一个字符串 <code>s</code> 、一个字符串 <code>t</code> 。返回 <code>s</code> 中涵盖 <code>t</code> 所有字符的最小子串。如果 <code>s</code> 中不存在涵盖 <code>t</code> 所有字符的子串，则返回空字符串 <code>""</code> 。</p><p><strong>注意：</strong>如果 <code>s</code> 中存在这样的子串，我们保证它是唯一的答案。</p><p> </p><p><strong>示例 1：</strong></p><pre><strong>输入：</strong>s = "ADOBECODEBANC", t = "ABC"<strong><br />输出：</strong>"BANC"</pre><p><strong>示例 2：</strong></p><pre><strong>输入：</strong>s = "a", t = "a"<strong><br />输出：</strong>"a"</pre><p> </p><p><strong>提示：</strong></p><ul>	<li><code>1 <= s.length, t.length <= 10<sup>5</sup></code></li>	<li><code>s</code> 和 <code>t</code> 由英文字母组成</li></ul><p> </p><strong>进阶：</strong>你能设计一个在 <code>o(n)</code> 时间内解决此问题的算法吗？
<p>以下错误的选项是？</p>
## aop
### before
```cpp
#include <bits/stdc++.h>
using namespace std;
```
### after
```cpp
int main()
{
    Solution sol;
    string s = "ADOBECODEBANC";
    string t = "ABC";
    string res;
    res = sol.minWindow(s, t);
    cout << res;
    return 0;
}

```

## 答案
```cpp
class Solution
{
public:
    string minWindow(string s, string t)
    {
        unordered_map<char, int> hs, ht;
        for (auto c : t)
            ht[c]++;

        string res;
        int cnt = 0;
        for (int i = 0, j = 0; i < s.size(); i++)
        {
            hs[s[i]]++;
            if (hs[s[i]] <= ht[s[i]])
                cnt++;

            while (hs[s[j]] > ht[s[j]])
                hs[s[j++]]--;
            if (cnt == t.size())
            {
                if (res.empty())
                    res = s.substr(j, i - j);
            }
        }

        return res;
    }
};
```
## 选项

### A
```cpp
class Solution
{
public:
    string minWindow(string s, string t)
    {
        vector<int> need(58, 0), window(58, 0);
        for (auto c : t)
            ++need[c - 'A'];
        int left = 0, right = 0;
        int count = 0;
        int target = 0;
        for (auto c : need)
        {
            if (c)
                ++target;
        }
        int start = 0;
        int len = INT_MAX;
        while (right < s.size())
        {
            auto c = s[right] - 'A';
            ++right;
            if (need[c] > 0)
            {
                ++window[c];
                if (need[c] == window[c])
                    ++count;
            }

            while (count == target)
            {
                if (right - left < len)
                {
                    start = left;
                    len = right - left;
                }
                auto c = s[left] - 'A';
                ++left;
                if (need[c] > 0)
                {
                    if (need[c] == window[c])
                        --count;
                    --window[c];
                }
            }
        }
        return len == INT_MAX ? "" : s.substr(start, len);
    }
};
```

### B
```cpp
class Solution
{
public:
    string minWindow(string s, string t)
    {
        unordered_map<char, int> findChar;
        int n1 = s.length(), n2 = t.length(), i, j;
        for (i = 0; i < n2; i++)
            findChar[t[i]]++;
        int start = 0, cnt = 0, minLength = n1 + 1, now = 0;
        for (i = 0; i < n1; i++)
        {
            if ((--findChar[s[i]]) >= 0)
                cnt++;
            if (cnt == n2)
            {
                while (++findChar[s[now]] <= 0)
                    now++;
                cnt--;
                if (i - now + 1 < minLength)
                {
                    start = now;
                    minLength = i - now + 1;
                }
                now++;
            }
        }
        return minLength > n1 ? "" : s.substr(start, minLength);
    }
};
```

### C
```cpp
class Solution
{
public:
    string minWindow(string s, string t)
    {
        string ans = "";
        map<char, int> lettercount;
        for (char c : t)
            ++lettercount[c];
        int count = 0, left = 0, minlen = INT_MAX;
        for (int i = 0; i < s.size(); ++i)
        {
            if (--lettercount[s[i]] >= 0)
                ++count;
            while (count == t.size())
            {
                if (minlen > i - left + 1)
                {
                    minlen = i - left + 1;
                    ans = s.substr(left, minlen);
                }
                if (++lettercount[s[left]] > 0)
                    --count;
                ++left;
            }
        }
        return ans;
    }
};
```