[LC-76][chapter3][Two Pointer Algorithm] Minimum Window Substring

[renchord]

Tag : 双指针 中文链接 : https://leetcode-cn.com/problems/minimum-window-substring/ 英文链接 : https://leetcode.com/problems/minimum-window-substring/

题目描述: 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

注意：

对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。 如果 s 中存在这样的子串，我们保证它是唯一的答案。   示例 1：

输入：s = "ADOBECODEBANC", t = "ABC" 输出："BANC" 示例 2：

输入：s = "a", t = "a" 输出："a" 示例 3:

输入: s = "a", t = "aa" 输出: "" 解释: t 中两个字符 'a' 均应包含在 s 的子串中， 因此没有符合条件的子字符串，返回空字符串。   提示：

1 <= s.length, t.length <= 105 s 和 t 由英文字母组成   进阶：你能设计一个在 o(n) 时间内解决此问题的算法吗？

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/minimum-window-substring 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解:

首先用滑动窗口的方法对示例1 进行一个简单分析：如果用模拟的方法来看， 我们用两个指针分别为left和right来表示当前滑动的窗口边界，则初始状态下left = 0, right = 0; 如下图所示中的绿色1 （使用黑色表示left, 用蓝色表示right，需要匹配） 之后我们需要不断地移动right，使得s [left, right]之间的所有字符出现的次数 > t 中所有字符出现的次数。 这里需要注意一点的是，t中的字符可能会出现多次，例如 t = "AAA"， 此时示例1的s中就找不到这样的子串来符合要求。

因此，我们很自然的想到，我们需要统计t中字符出现的次数，以及当前滑动窗口内字符出现的次数，我们使用一个hash表来完成统计。（诚然我们也可以利用char的大小在256以内直接使用常量规模的数组来统计，此处按下不表。） 我们可以按照如下方式声明：

unordered_map <char, int> expected_times;  //expected_times['A'] 表示字符'A'在t中出现的次数，这是一个常量
unordered_map <char, int> appeared_times; //appeared_times['A'] 表示字符'A'在当前窗口中出现的次数，这是一个变量

那么我们也会很自然的想到初始化 exptected_times的方法：

for(int i = 0; i < t.size(); ++i)
     expected_times[t[i]]++;

对于appeared_times的操作方法： 当我们移动right指针(right++)， appeared_times[s[right]]++; 当我们移动left指针(--left) appeared_times[s[left]]--; 此处不再解释left, right和数组操作时的对应关系。

重头戏来了！！！！！！ 《当我们谈更新right指针时，我们谈些什么？》 每当维护了right指针并更新了appeared_times后，如果当前的窗口已经满足了可以包括所有的t中出现的字符，那么我们可以尝试去移动left指针来最小化这个窗口。 问题来了，我们如何去方便的表示 “当前的窗口已经满足了可以包括所有的t中出现的字符” 这一条件呢？ 如果我们需要对t中每一个字符X 都要确保 appeared_times[X] >= expected_times[X]，那未免也太麻烦了。 因此，我们设计一个变量叫 validcnt， 当validcnt == t.size() 时，就认为 “当前的窗口已经满足了可以包括所有的t中出现的字符”。 什么时候去增加这个validcnt呢？ 聪明的你可以推断出来，我们只会在以下这种情形来增加validcnt: right指针所指的字符为X， 当 appeared_times[X] < expected_times[X]时，才会 validcnt++; 如果right所指的X已经存在appeared_times[X] >= expected_times[X]时，不会增加validcnt; 因此当validcnt == t.size()时，则代表所有的expected_times[]都被满足； 关于right指针时我们还剩下最后一件事情没有讨论，则如果right所指的字符为X，而expected_times[X] <= 0, 即从未在t中出现过，那我们也完全不用管这个字符，它不会对validcnt产生影响，也不会影响后续判断left指针的移动。

第二个重头戏来了！！！！！ 《当我们谈更新left指针时，我们谈些什么？》 当然最重要的前提是，什么时候开始更新left指针？ OK，很显然时当 “当前的窗口已经满足了可以包括所有的t中出现的字符” ，上面我们已经把这个条件简化成了 validcnt == t.size()； 以下图中的绿色2为标记，此时我们可以尝试去移动left指针了； 我们真的可以移动left让它++吗？ 显然不可以，因为left此刻所指的字符A的apperead_times 和 expected_times相等 因此移动left的一个充分条见是 apperaed_times[A] > expected_times[A]; 还记得上面讨论的t不关心的字符，即expcted_times[A] == 0的字符A，也可以移动left；这是另一个充分条见 移动left要做的事情：

--appeared_times[s[left]];
++left;

只要满足了 上面两个充分条件之一，我们都可以不断的移动left指针； 当我们无法移动left指针时，我们需要记录当前 left的位置，以及[left, right] 涵盖的距离以便于我们最后返回答案。 很显然我们需要取最小的[left, right]距离，因此只有在新值 < 旧值时才需要更新我们的答案。

根据上面的分析，我们从阶段2开始尝试移动left指针，但失败，因此我们更新我们的答案： rst_start_idx = 0, width = 6; 我们继续更新right指针，一直到阶段4，中间我们会路过阶段3，此时这个B由于 appeared_times[B] 不满足 < expected_times[B]，我们不会对validcnt进行++； 在阶段4，我们终于可以更新left指针了，我们一直可以更新它直到 left == 5，阶段6，我们会路过阶段4，此时left会跳过5，因为我们在路过阶段3时会对appeared_times[B]进行++更新（虽然我们不更新validcnt）； 在阶段6，我们不可以再更新left指针了； 我们继续更新right指针，一直到阶段7，validcnt不会更新，但更新了apperaed_times[C]，我们又可以去移动left指针指到阶段8； 在阶段8，我们不再可以更新left指针了，但可以更新答案 rst_start_idx= 9, width =4； 注意，在这个过程中有多次更新rst_start_idx和width,此处就不再展开啦。

最终代码：

class Solution {
public:
    string minWindow(string s, string t) {

        unordered_map <char, int> expected_times;
        unordered_map <char, int> appeared_times;

        if(s.size() == 0)
            return "";
        if(s.size() < t.size())
            return "";

        for(int i = 0; i < t.size(); ++i)
            expected_times[t[i]]++;

        int left = 0;
        int width = INT_MAX, rst_start_idx = 0;
        int validcnt = 0;

        for(int right = 0; right < s.size(); ++right)
        {
            if(expected_times[s[right]] > 0)
            {

                if(appeared_times[s[right]] < expected_times[s[right]])
                    ++validcnt;
                ++appeared_times[s[right]]; // This char appear times +1 in this substr;
            }
            if(validcnt == t.size()) // now we may move the left pointer to right as we can
            {
                while(appeared_times[s[left]] > expected_times[s[left]] || expected_times[s[left]] == 0)
                {
                  --appeared_times[s[left]];
                  ++left;
                }
                if(width > right - left + 1)
                {
                    rst_start_idx = left;
                    width = right -left + 1;
                }
            }
        }

        return width == INT_MAX ? "" : s.substr(rst_start_idx, width);

    }
};

空间复杂度分析 : O(n),这是两个map所用的空间 时间复杂度分析: O(n), 双指针遍历数组，最多n的时间复杂度。