# Time limit exceed though O(n) algo using C++

• ``````class Solution {
public:

string minWindow(string S, string T) {
string ret;
if(!S.compare("")  ||  !T.compare("")){
return "";
}
vector<list<int> > window;
window.resize(256);
int hashT[256] = {0};
for(int i=0; i < T.length(); i++) hashT[T[i]]++;

int numChars = T.length();
list<int> wState;
int ansInd = -1; int ansL;
for(int i=0; i < S.length(); i++){
char c = S[i]; int hkey = c;
if(hashT[hkey] <= 0) continue;

wState.push_back(i);
if( window[hkey].size() < hashT[hkey] ){
numChars--;
window[hkey].push_back(i);
}
else{
window[hkey].pop_front();
window[hkey].push_back(i);
}

if(numChars == 0){
while(1){ //check if wState is latest
int ind = wState.front();
char c = S[ind];
if( window[c].front() == ind) break;
else{
wState.pop_front();
}
}

if( ansInd == -1 || (i - wState.front()+1) < ansL ){
ansInd = wState.front();
ansL = i - ansInd + 1;
}
}
}

if(ansInd == -1) return "";
else return S.substr(ansInd,ansL);

}
};
``````

Gives time limit exceed. I think the algorithm is O(n). I do have some data keeping which is not necessary. But somebody point out what talking a large amount of time. My initial guess was the C++ STL data structures are taking time to insert/delete data (and that is causing the error) ?

• Guess run into some infinite loop for some input?

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