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.

输入描述

输入满足以下条件：

• m == s.length
• n == t.length
• 1 <= m, n <= 105
• s and t consist of uppercase and lowercase English letters.

示例

输入

s = "ADOBECODEBANC", t = "ABC"

输出

"BANC"

解释

The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t.

分析

显然，可以通过枚举区间的起点和终点暴力解决这个问题，但时间复杂度过高，是否存在一种只需遍历一遍字符串就能得到结果的方法呢？

利用滑动窗口的思想，就可以扫描一遍字符串求解该问题。

本题的滑动窗口解法的伪码如下：

string s, t;
    // 在 s 中寻找 t 的「最小覆盖子串」
    int left = 0, right = 0;
    string res = s;
    
    while(right < s.size()) {
        window.add(s[right]);
        right++;
        // 如果符合要求，说明窗口构造完成，移动 left 缩小窗口
        while (window 符合要求) {
            // 如果这个窗口的子串更短，则更新 res
            res = minLen(res, window);
            window.remove(s[left]);
            left++;
        }
    }
    return res;

目前已经明确了可以通过一遍扫描字符串解决问题，那该如何高效的判断当前窗口是否满足要求就成为了问题的关键。我们可以维护一个字典来实现满足要求的判定。

AC代码

class Solution
{
public:
    string minWindow(string s, string t)
    {
        unordered_map<char, int> tm;
        for (auto i : t)
            tm[i]++;
        int l = 0, r = 0;
        int ansl, len = -1, cnt = 0;
        while (r < s.size())
        {
            if (tm.find(s[r]) != tm.end())
            {
                if (tm[s[r]] > 0)
                    cnt++;
                tm[s[r]]--;
            }
            while (cnt == t.size() && l <= r)
            {
                if (len == -1 || len > r - l + 1)
                {
                    len = r - l + 1;
                    ansl = l;
                }
                if (tm.find(s[l]) != tm.end())
                {
                    if (tm[s[l]] >= 0)
                        cnt--;
                    tm[s[l]]++;
                }
                l++;
            }
            r++;
        }
        return len == -1 ? "" : s.substr(ansl, len);
    }
};