最小覆盖子串

这道题目用到了滑动窗口这一大杀器，它可以解决如下问题：

1. 最小覆盖子串（LeetCode76）
2. 字符串排列（LeetCode567）
3. 统计字母异位词（LeetCode438）
4. 最长无重复子串（LeetCode3）

滑动窗口的基本思想：

1. 用两个字典分别维护窗口中字符的统计数量、以及被求解子串中字符的统计数量
2. 用双指针遍历主字符串，双指针的初始值均为0，窗口的范围是[left, right)（左闭右开）
3. 遍历过程中，不断增大、缩小窗口，并更新状态

下面是滑动窗口的基本模版(其中...需要根据题目要求进行修改)：

void window(string s, string t) {
    unordered_map<char, int> window, target;
    for (char c : t) { ++target[c]; }
    int left = 0, right = 0;    // 初始化双指针
    ...                         // 定义状态值
    while (right < s.size()) {
        // 增大窗口
        char c = s[righ]
        ++right;
        ...                     // 更新window
        while (达到缩小窗口的条件) {
            ...                 // 更新状态值
            char c = s[left];
            ++left;
            ...                 // 更新window/状态值
        }
    }
}

本题代码如下：

//
// Created by jt on 2020/9/1.
//
#include <string>
#include <unordered_map>
using namespace std;

class Solution {
public:
    /**
     *
     * @param S string字符串
     * @param T string字符串
     * @return string字符串
     */
    string minWindow(string S, string T) {
        // write code here
        unordered_map<char, int> window, target;
        for (char c : T) ++target[c];
        int left = 0, right = 0;
        int start = 0, minLen=INT32_MAX;
        int count = 0;      // 记录窗口中字符是否满足目标
        while (right < S.size()) {
            char c = S[right];
            ++right;
            if (target.count(c)) {
                ++window[c];
                if (window[c] == target[c]) ++count;
            }
            while (count == target.size()) {
                if (right-left < minLen) {
                    start = left;
                    minLen = right-left;
                }
                c = S[left];
                ++left;
                if (target.count(c)) {
                    if (window[c] == target[c]) --count;
                    --window[c];
                }
            }
        }
        return minLen==INT32_MAX ? "" : S.substr(start, minLen);
    }
};