Solution Using Queue and Map O(N) With Explanation

• `````` 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);
}``````

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