Solution Using Queue and Map O(N) With Explanation


  • 0
    C
     bool contains_all(unordered_map<char,int> &m){
        // this function returns whether our current window contains all required characters
        for(auto it = m.begin();it!=m.end();it++){
            if(it->second < 0) //negative count means we still need more of that character
                return false;
        }
        return true;
    }
    string minWindow(string s, string t) {
        unordered_map<char,int> m;
        if(t.size()>s.size()) return "";
        for(char c:t){ // all characters in t are required. so if t is "aac", m[a]=-2 and m[c] = -1
            if(m.find(c)==m.end())
                m[c] = -1;
            else
                m[c]--;
        }
        queue<int> q; // will hold all possible starts of windows
        int minlen = INT_MAX; // length of the minimum window
        int minstart = -1; // start index of the minimum window
        for(int i=0;i<s.size();i++){
            char c = s[i];
            if(m.find(c)!=m.end()){// if character exists in c
                m[c]+=1; // increase the characters present count in the current window
                q.push(i); // the position could be the start of a future window
                while(contains_all(m)){ // for all existing valid windows (window is valid if all required counts are +)
                    int newlen = i-q.front()+1; //length of new window
                    if(newlen<=minlen){
                        minlen = newlen;
                        minstart = q.front();
                    }
                    // once we find a window, we check for more windows by moving to the next possible start 
                    char start = s[q.front()];
                    m[start]-=1; // since we remove our start character from the window, we decrease its count
                    q.pop();
                }
            }
        }
        if(minstart == -1) return "";
        return s.substr(minstart,minlen);
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.