Minimum Window Substring

解题思路

  1. 本质上还是双指针；

  2. 构造一个滑动窗口，先移动右指针，使得能够包含目标字符串，然后再尝试移动左指针，使得包含失效，再继续移动右指针，在这个过程中，记录目标解；

  3. 剩下的就是代码实现上的细节了。

代码

class Solution {
public:
    string minWindow(string s, string t) {
        vector<int> remained(128, 0);
        for (auto c : t) {
            remained[c]++;
        }
        int left = 0, right = 0, start = 0, minL = INT_MAX;
        int need = t.size();
        while (right < s.size()) {
            if (remained[s[right]]-- > 0) {
                need--;
            }
            right++;
            while (need == 0) {
                if (right - left < minL) {
                    minL = right - left;
                    start = left;
                }
                if (remained[s[left]]++ == 0) {
                    need++;
                }
                left++;
            }
        }
        return (minL == INT_MAX) ? "":s.substr(start, minL);
    }
};