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

        for(int i = 0; i < (int) t.size(); i++) {
            m_t[t[i]]++;
            exist[t[i]] = 1;
        }
        int req = (int) m_t.size();

        int j = 0;
        int min_length = 2e9, idx1 = 0, idx2 = 0;
        for(int i = 0; i < (int) s.size(); i++) {
            while(req > 0 and j < (int) s.size()) {
                if(exist[s[j]] == 1) {
                    m_t[s[j]]--;
                    if(m_t[s[j]] == 0) {
                        req--;
                    }
                }


                j++;
            }

            if(req == 0) {
                if(min_length > j - i) {
                    min_length = j - i ;
                    idx1 = i;
                    idx2 = j;
                }
            }
            if(exist[s[i]]) {
                m_t[s[i]]++;
                if(m_t[s[i]] > 0) {
                    req++;
                }
            }


        }
        if(min_length == 2e9) {
            return "";
        }
        string ret = "";
        for(int i = idx1; i < idx2; i++) {
            ret += s[i];
        }

        return ret;

    }
};