Description

Submission

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

        int l = 0, r = 0;
        int minL = 0, minR = s.size();
        int remaining = counter.size();
        for(; r < s.size(); ++r) {
            if(counter.find(s[r]) != counter.end()) {
                counter[s[r]]--;
                if(counter[s[r]] == 0) remaining--;
            }
            if(remaining == 0) {
                // shrinking the window size by moving left forward
                while(l < r) {
                    auto iter = counter.find(s[l]);
                    if(iter == counter.end()) {
                        l++;
                    } else if(iter->second < 0) counter[s[l++]]++;
                    else break;
                }

                if(r - l < minR - minL) {
                    minR = r;
                    minL = l;
                }

                // move the left forward
                counter[s[l++]]++;
                remaining++;
            }
        }
        if(minR - minL == s.size()) return "";
        return s.substr(minL, minR - minL + 1);
    }
};

References

1. https://www.youtube.com/watch?v=eS6PZLjoaq8