76. Minimum Window Substring

LeetCode

这篇文章意在教你使用滑动窗口模板一步一步解决本题，相比直接给出完整代码，这样更容易让你弄懂解决一个问题该怎么做。

滑动窗口模板

int left = 0, right = 0;

while (right < s.size()) {
    // window.add(s[right]);
    right++;

    while (窗口满足条件) {
        // minimize the substring
        // window.remove(s[left]);
        left++;
    }
    // maximize the substring
}
  1. 初始化 left = 0 和 right = 0，它们维持一个滑动窗口
  2. 每次迭代增加 right 向右扩展窗口
  3. 如果窗口满足条件，不断增加 left 缩小窗口，直到窗口内的字符串不满足条件
  4. 重复2和3，直到 right 抵达尽头

TODO：说明什么情况下才可以套用滑动窗口模板

Step By Step Solution

1. 套模板

class Solution {
public:
    string minWindow(string s, string t) {
        // initial the sliding window index
        int left = 0, right = 0;
        
        // intial the minimum window index
        int start = 0, minLen = INT_MAX;
        
        while (right < s.size()) {
            // TODO: window.add(s[right])
            right++;
            
            while (the sliding window meets the condition) {
                // TODO: minimize
                // TODO: window.remove(s[left])
                left++;
            }
        }
        
        return minLen == INT_MAX ? "" : s.substr(start, minLen);
    }
};

2. 初始化滑动窗口

我们要令最小化一个滑动窗口，使得这个窗口内的词频等于t的词频。直觉告诉我们可以使用两个哈希表去分别存储这两个窗口的词频。

class Solution {
public:
    string minWindow(string s, string t) {
        int left = 0, right = 0;
        int start = 0, minLen = INT_MAX;
        
        // initial the dynamic characters frequency counter
        unordered_map<char, int> window;
        unordered_map<char, int> need;
        for (char c : t) {
            need[c]++;
        }
        
        while (right < s.size()) {
            // TODO: window.add(s[right])
            right++;
            
            while (the sliding window meets the condition) {
                // TODO: minimize
                // TODO: window.remove(s[left])
                left++;
            }
        }
        
        return minLen == INT_MAX ? "" : s.substr(start, minLen);
    }
};

3. 完成add, remove和condition

根据题意，当滑动窗口内的词频等于t的词频时，滑动窗口有效。所以我们需要一个计数器match来统计达到要求的字符个数。

另外，我们只处理在t中出现过的字符，没出现过的一律忽略不作处理。

class Solution {
public:
    string minWindow(string s, string t) {
        int left = 0, right = 0;
        int start = 0, minLen = INT_MAX;
        
        unordered_map<char, int> window;
        unordered_map<char, int> need;
        for (char c : t) {
            need[c]++;
        }
        
        int match = 0;
        while (right < s.size()) {
            // window.add(s[right])
            char r = s[right];
            if (need.count(r)) {
                window[r]++;
                if (window[r] == need[r]) {
                    match++;
                }
            }
            right++;
            
            while (match == need.size()) {
                // TODO: minimize
                // window.remove(s[left])
                char l = s[left];
                if (need.count(l)) {
                    window[l]--;
                    if (window[l] < need[l]) {
                        match--;
                    }
                }
                left++;
            }
        }
        
        return minLen == INT_MAX ? "" : s.substr(start, minLen);
    }
};

4. 最小化滑动窗口index

class Solution {
public:
    string minWindow(string s, string t) {
        int left = 0, right = 0;
        int start = 0, minLen = INT_MAX;
        
        unordered_map<char, int> window;
        unordered_map<char, int> need;
        for (char c : t) {
            need[c]++;
        }
        
        int match = 0;
        while (right < s.size()) {
            char r = s[right];
            if (need.count(r)) {
                window[r]++;
                if (window[r] == need[r]) {
                    match++;
                }
            }
            right++;
            
            while (match == need.size()) {
                // minimize
                if (right - left < minLen) {
                    start = left;
                    minLen = right - left;
                }
                
                char l = s[left];
                if (need.count(l)) {
                    window[l]--;
                    if (window[l] < need[l]) {
                        match--;
                    }
                }
                left++;
            }
        }
        
        return minLen == INT_MAX ? "" : s.substr(start, minLen);
    }
};

Final Version

class Solution {
public:
    string minWindow(string s, string t) {
        int left = 0, right = 0;
        int start = 0, minLen = INT_MAX;
        
        unordered_map<char, int> window;
        unordered_map<char, int> need;
        for (char c : t) need[c]++;

        int matchChar = 0;
        while (right < s.size()) {
            // window.add(s[right])
            char r = s[right];
            if (need.count(r)) {
                window[r]++;
                if (window[r] == need[r]) {
                    matchChar++;
                }
            }
            right++;

            // condition for making the sliding window legal
            while (matchChar == need.size()) {
                // minimize the length of the window
                if (right - left < minLen) {
                    start = left;
                    minLen = right - left;
                }

                // window.remove(s[left])
                char l = s[left];
                if (need.count(l)) {
                    window[l]--;
                    if (window[l] < need[l]) {
                        matchChar--;
                    }
                }
                left++;
            }
        }
        
        return minLen == INT_MAX ? "" : s.substr(start, minLen);
    }
};