# Got "Timeout" on this solution???

• // The basic idea is that when we shrink window, we skip the letters which are not in T
// My test is good.
// Get timeout in leetcode
class Solution
{
public:
string minWindow(string S, string T) {
string result;
if(S.empty() || T.empty()){
return result;
}

if (S.length() < T.length())
return result;

unordered_map<char, int> map;
unordered_map<char, int> window;
for(int i = 0; i < T.length(); i++){
map[T[i]]++;
}

queue < int, list < int > > search_queue;
int start = 0;
int end = 0;
int count = 0;
int min_len = S.length() + 1;
char token = 0;

while ( start <= S.length() - T.length() && map.find(S[start]) == map.end())
{
++start;
}

if ( start > S.length() - T.length() )
return result;

count = 1;
if ( count == T.length() )
{
result = S.substr(start, count);
return result;
}

search_queue.push(start);

window[S[start]] = 1;
end = start + 1;

while ( end < S.length() )
{
if (map.find(S[end]) == map.end())
{
++end;
continue;
}

search_queue.push(end);

if (window.find(S[end]) == window.end())
{
window[S[end]] = 1;
}
else
{
window[S[end]] += 1;
}

if (window[S[end]] == map[S[end]])
{
++count;

while (count == map.size())
{
int len = end - start + 1;
if (min_len > len)
{
min_len = len;
result = S.substr(start, len);
}

if (search_queue.empty())
return result;
start = search_queue.front();
search_queue.pop();

window[S[start]] -= 1;
if (window[S[start]] < map[S[start]])
{
--count;
if (search_queue.empty())
return result;
}
start = search_queue.front();
// while (count == T.length())
}
// if (window[S[end]] == map[S[end]])
}
++end;
}

return result;
}

};

• Please ignore the question. I found a bug in it.

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