class Solution {
public:
    string minWindow(string s, string t) {
        map<char, int> required;
        map<char, bool> exist;

        for(int i = 0; i < (int) t.size(); i++) {
            required[t[i]]++;
            exist[t[i]] = true;
        }
        int valid_substring = (int) exist.size();
        int j = 0;
        int min_length = 1e9;
        int S, E;
        for(int i = 0; i < (int) s.size(); i++) {
            while(valid_substring > 0 and j < (int) s.size()) {
                if(exist[s[j]]) {
                    required[s[j]]--;

                    if(required[s[j]] == 0) {
                        valid_substring--;
                    }
                }
                j++;
            }
            if(valid_substring == 0) {
                if(min_length > j - i + 1) {
                    min_length = j - i + 1;
                    S = i;
                    E = j;
                }
            }
            if(exist[s[i]]) {
                required[s[i]]++;
                if(required[s[i]] > 0) {
                    valid_substring++;
                }
            }
        }
        if(min_length == 1e9) {
            return "";
        }
        string res = "";
        for(int i = S; i < E; i++) {
            res += s[i];
        }

        if(min_length == 1e9) {
            return "";
        }
        return res;
    }
};