Time Limit Exceeded Error


  • 0
    N

    How should I change the following code to avoid time limit exceeded error? Even sliding window solutions iterate over string s for s.size()-p.size()+1 time.

    vector<int> findAnagrams(string s, string p) {
            int len = p.size();
            vector<int> ans;
            if(p.size()>s.size())return ans;
            sort(p.begin(), p.end());
            for(int i = 0 ; i < s.size()-p.size()+1;++i){
                string temp = s.substr(i,len);
                sort(temp.begin() , temp.end());
                if(temp==p){ans.push_back(i);}
                
            }
            return ans;
        }
    

  • 0
    N

    @nhoss003 I think I figured it out. It is because I am sorting each substring in the for loop which is very inefficient. consider size of the pattern to be p. so each sorting takes p log(p) time and consider size of the text is s so overall it takes s/p * p log(p). But in the sliding window solution time complexity is of o(s) because in the for loop each time we change two values in the vector, which is o(1) and we do this for s - p times, so overall o(s).


Log in to reply
 

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