# C++ solution, beats 99% O(s.size())

• ``````class Solution {
public:
vector<int> findSubstring(string s, vector<string>& words) {
vector<int> ans;
if(words.empty() || words[0].empty()) return ans;
unordered_map<string,int> cnt;   /*Here we use cnt to count the number
of times that a string appears in words*/
int n = s.size(), l = words[0].size(), m = words.size();
for(auto w:words) cnt[w]++;
auto f = [&cnt, &ans, &s, n, l, m](int i){ /*This is a feature of C++11,
using Lambda function, we can capture things instead of passing so many arguments.
This function do: we start from an index "i", and increase the length of window
by "words[0].size()" every time, meanwhile counting all the possible starting
points that makes the window cover all the words. The complexity of this function
call is O(s.size()/words[0].size()).*/
int b = i, e = i;
unordered_map<string,int> pl;
while(e <= n-l){
string tmp = s.substr(e,l);
e += l;
if(!cnt.count(tmp)){
b = e;
pl.clear();
}
else if(pl[tmp] == cnt[tmp]){
while(s.substr(b,l) != tmp){
pl[s.substr(b,l)]--;
b += l;
}
b += l;
}
else{
pl[tmp]++;
if(e - b == l*m){
ans.push_back(b);
pl[s.substr(b,l)]--;
b += l;
}
}
}
};
for(int i=0;i<l;++i) f(i); /* We call that function "words[0].size()" times,
which can cover all the possible configurations. Then the complexity is O(s.size()).*/
return ans;
}
};
``````

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