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


  • 0
    N
    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) ?


  • 0
    G

    Guess run into some infinite loop for some input?


Log in to reply
 

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