题目描述

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).

样例

Input: S = "ADOBECODEBANC", T = "ABC"
Output: "BANC"

算法1

滑动窗口法 $O(n)$

类型题 双指针 + hashtable
用hashmap char->int 存char在T中的出现次数，双指针遍历S

当hash[c] > 0，则c在T中的，并且还没有在window中被包含的个数为hash[c]
当hash[c] < 0, 则c在window中有多余的出现
当hash[c] = 0, 则c要么不在T中， 要么恰巧被包含了T中的需要的个数。

C++ 代码

    string minWindow(string s, string t) {
        unordered_map<char, int> hash;
        for(auto c : t) hash[c]++;

        int total = hash.size(); // T中unique的char的数量

        int count = 0; // 在window中包含的T的unique char的个数。
        string res = "";

        for(int i=0, j=0; j<s.size(); j++) {
            hash[s[j]] --;

            // 若count[s[j]] 被减到0，说明s[j]是T中的，即使在T中出现n次，也全部被window包含了
            if(hash[s[j]] == 0) count++;

            // 前移i，检查 s[i] 是否在T中且是多余的char，或者是不在T中的char。
            // 如果是在T中且多余的char, 则增加到0之前都是多余的
            // 如果是不在T中的char, 则前面j经过该位置时，将其--，现在可以++直到0
            while( hash[s[i]] < 0) hash[s[i++]] ++; 

            // 若全部都包含，且res为空或者更长
            if(count == total && (res.empty() || res.size() > j-i+1)) res = s.substr(i, j-i+1);
        }

        return res;
    }

类似的题目:
https://leetcode.com/problems/minimum-window-substring/
https://leetcode.com/problems/longest-substring-without-repeating-characters/
https://leetcode.com/problems/substring-with-concatenation-of-all-words/
https://leetcode.com/problems/longest-substring-with-at-most-two-distinct-characters/
https://leetcode.com/problems/find-all-anagrams-in-a-string/