# C++ O(n) Solution beats 99%

• Main idea is to transform the problem into finding longest sub-array problem. Different offset of the starting position modulo length of word should be considered separately.

``````class Solution {
public:
vector<int> findSubstring(string s, vector<string>& words) {
int n = s.size();
int nWords = words.size();
if (nWords == 0) return vector<int>();
int len = words[0].size();

unordered_map<string,int> wordMap;
for (int i = 0, id = 0; i < nWords; ++i) {
auto it = wordMap.find(words[i]);
if (it == wordMap.end()) {
wordMap.emplace(words[i], id++);
}
}

vector<int> wordCount(wordMap.size(), 0);
for (int i = 0, id = 0; i < nWords; ++i) {
wordCount[wordMap[words[i]]]++;
}

vector<int> occur(n, -1);
for (int i = 0; i < n - len + 1; ++i) {
auto it = wordMap.find(s.substr(i, len));
if (it != wordMap.end()) {
occur[i] = it->second;
}
}

int nDistWords = wordMap.size(); // Number of distinct words
vector<int> ret;

for (int r = 0; r < len; ++r) {
vector<int> curWordCount(nDistWords);
int curLength = 0;

for (int i = r; i < n; i += len) {
int index = occur[i];
if (index >= 0) {
if (curWordCount[index] < wordCount[index]) {
++ curLength;
++ curWordCount[index];
} else {
while (occur[i - curLength * len] != index) {
-- curWordCount[occur[i - curLength * len]];
-- curLength;
}
}

if (curLength == nWords)
ret.push_back(i - (nWords - 1) * len);
} else {
if (curLength > 0) {
memset(curWordCount.data(), 0, nDistWords * sizeof(int));
curLength = 0;
}
}
}
}

return ret;
}
};
``````

• Looks good. Now I understand why I exceeded time. I did not use map struct to deduplicate the words.

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