You are given a string, s, and a list of words, words, that are all of the same length. Find all starting indices of substring(s) in s that is a concatenation of each word in words exactly once and without any intervening characters.
Example 1:
Input:
s = "barfoothefoobarman",
words = ["foo","bar"]
Output: [0,9]
Explanation: Substrings starting at index 0 and 9 are "barfoor" and "foobar" respectively.
The output order does not matter, returning [9,0] is fine too.
Example 2:
Input:
s = "wordgoodgoodgoodbestword",
words = ["word","good","best","word"]
Output: []
vector<int> findSubstring(string s, vector<string>& words) { // time: O(str_len * (# of words)); space: O(# of words)
vector<int> res;
if (s.empty() || words.empty()) return res;
int n = words.size(), m = words[0].size();
unordered_map<string, int> m1;
for (const string& word : words) ++m1[word];
for (int i = 0; i < s.length() - n * m; ++i) {
unordered_map<string, int> m2;
int j = 0;
for (; j < n; ++j) {
string t = s.substr(i + j * m, m);
if (!m1.count(t)) break;
++m2[t];
if (m2[t] > m1[t]) break;
}
if (j == n) res.push_back(i);
}
return res;
}
vector<int> findSubstring(string s, vector<string>& words) { // time: O(cnt + n); space: O(cnt)
vector<int> res;
if (s.empty() || words.empty()) return res;
int n = s.size(), cnt = words.size(), len = words[0].size();
unordered_map<string, int> m1;
for (string& str : words) ++m1[str];
for (int i = 0; i < len; ++i) {
int left = i, count = 0;
unordered_map<string, int> m2;
for (int j = i; j <= n - len; j += len) {
string t = s.substr(j, len);
if (m1.count(t)) {
++m2[t];
if (m2[t] <= m1[t])
++count;
else {
while (m2[t] > m1[t]) {
string t1 = s.substr(left, len);
--m2[t1];
if (m2[t1] < m1[t1]) --count;
left += len;
}
}
if (count == cnt) {
res.push_back(left);
--m2[s.substr(left, len)];
--count;
left += len;
}
} else {
m2.clear();
count = 0;
left = j + len;
}
}
}
return res;
}