Minimum Window Substring

https://leetcode.com/problems/minimum-window-substring/description/

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

For example, S="ADOBECODEBANC" T="ABC"

Minimum window is"BANC".

Note: If there is no such window in S that covers all characters in T, return the empty string"".

If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.

Thoughts

问数组内满足条件的子数组的最小size，标准动态滑动窗口问题。r照例不断往前移动, 但在没找到permutation前, l都维持不动. 当permutation找到后, 把l不断往前移动到permutation开始的地方, 即略过那些不在permutation中的元素. 这时看新窗口的长度是多少, 如果是最小则存下来. 然后再让l往前一格, 重新寻找以新l为开头的包含permutation的r能在哪. 重复此过程.

统计几样元素的个数是否够，用freq map。先根据个数置为相应的负数，代表欠缺这些。当==0意味着对应元素个数满足。配合另一个计数cursize记录当前满足条件的总个数，遍历到i且freq[i] <= 0时++cursize, 表面找到一个顶用的；当移出i且freq[i] == 0时，意味着移出会让顶用的少一个, --cur_size; cur_size == t.size()意味着当前块满足所需。

Code

/*
 * @lc app=leetcode id=76 lang=cpp
 *
 * [76] Minimum Window Substring
 */
class Solution {
public:
    string minWindow(string s, string t) {
        int l = 0, r = 0, min_len = s.size(), cur_size = 0;
        string res = "";
        unordered_map<char, int> freq;
        for (char c : t) {
            if (!freq.count(c)) freq[c] = 0;
            --freq[c];
        }
        while (r < s.size()) {
            const auto cr = s[r];
            if (!freq.count(cr)) freq[cr] = 0;
            ++freq[cr];
            if (freq[cr] <= 0) {
                ++cur_size;
            }
            while (cur_size == t.size()) {
                const auto cl = s[l];
                if (r - l + 1 <= min_len) {
                    min_len = r - l + 1;
                    res = s.substr(l, min_len);
                }
                if (freq[cl] == 0) {
                    --cur_size;
                }
                --freq[cl];
                ++l;
            }
            ++r;
        }
        return res; 
    }
};

Analysis

时间复杂度O(s.len), l和r最多走这么多. 空间O(1).