# Time Limit Exceeded. A very normal algorithm...

• ``````class Solution {
public:
vector<int> findSubstring(string S, vector<string> &L) {
//There may be duplicate words in L
int Ssize = S.size();
int m = L.size();
int k = L[0].size();
unordered_map<string, int> word;
vector<int> res;
for(int i = 0; i < m; ++i)
word[L[i]]++;
for(int i = 0; i <= Ssize - k * m; ++i) {//if I use i <= S.size() - k * m directly, it is wrong because S.size() is                                      //                                               the type of size_t
if(word.find(S.substr(i, k)) == word.end())
continue;
else {
unordered_map<string, int> hm = word;
int j = i;
while(true) {
if(hm.find(S.substr(j, k)) == hm.end())
break;
else {
if(hm[S.substr(j, k)] == 1)
hm.erase(S.substr(j, k));
else
hm[S.substr(j, k)]--;
j += k;
if(hm.size() == 0) {
res.push_back(i);
break;
}
}
}
}
}
return res;
}
};
``````

Time Limit exceeded when meet a very long test case.

My algorithm is naive. use a map to store the string and it's number. and minus one when meet a string in S. if reduce to one, then remove this item from the map.

• Your algorithm is brute force time complexity is `O((M - N) * N)`, letting M be length of S and N be length of L array. So it won't pass all test case. The best solution is `O(M * Len)`, where Len is the length of string in L.

Have you ever solved this Minimum Window Substring ? It may help you to come up a better solution.

To solve Minimum Window Substring, you can read this article.

• I don't think it's because my algorithm because others who use the same algorithm has been accepted(like http://n00tc0d3r.blogspot.com/search?q=Permutations#!/2013/06/substring-with-concatenation-of-all.html).

• I get your problem. You over used `S.substr(j, k)`, it will cost time everytime. You should save it to a temp variable, then use this variable instead of `S.substr(j, k)`.

• Yes! It has been accepted! I will focus on such details later! Thank you sooooooo much!!

• But I don't think make such a change will reduce the time complexity in big O notation, right?
In addition, if substr(begin, len) is O(len), the total time is `(S.size() - L.size()*L[0].size()) * L.size()*L[0].size()`, right?

• Minimum Window Substring is right

• “ if(word.find(S.substr(i, k)) == word.end())
continue; ”
This sentence is the key, it can avoid the unnecessary copy of the map

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