# 30. Substring with Concatenation of All Words

You are given a string `s` and an array of strings `words`. All the strings of `words` are of the same length.

A concatenated substring in `s` is a substring that contains all the strings of any permutation of `words` concatenated.

• For example, if `words = ["ab","cd","ef"]`, then `"abcdef"`, `"abefcd"`, `"cdabef"`, `"cdefab"`, `"efabcd"`, and `"efcdab"` are all concatenated strings. `"acdbef"` is not a concatenated substring because it is not the concatenation of any permutation of `words`.

Return the starting indices of all the concatenated substrings in`s`. You can return the answer in any order.

Example 1:

``````**Input:** s = "barfoothefoobarman", words = ["foo","bar"]
**Output:** [0,9]
**Explanation:** Since words.length == 2 and words[i].length == 3, the concatenated substring has to be of length 6.
The substring starting at 0 is "barfoo". It is the concatenation of ["bar","foo"] which is a permutation of words.
The substring starting at 9 is "foobar". It is the concatenation of ["foo","bar"] which is a permutation of words.
The output order does not matter. Returning [9,0] is fine too.
``````

Example 2:

``````**Input:** s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
**Output:** []
**Explanation:** Since words.length == 4 and words[i].length == 4, the concatenated substring has to be of length 16.
There is no substring of length 16 in s that is equal to the concatenation of any permutation of words.
We return an empty array.
``````

Example 3:

``````**Input:** s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
**Output:** [6,9,12]
**Explanation:** Since words.length == 3 and words[i].length == 3, the concatenated substring has to be of length 9.
The substring starting at 6 is "foobarthe". It is the concatenation of ["foo","bar","the"] which is a permutation of words.
The substring starting at 9 is "barthefoo". It is the concatenation of ["bar","the","foo"] which is a permutation of words.
The substring starting at 12 is "thefoobar". It is the concatenation of ["the","foo","bar"] which is a permutation of words.
``````

Constraints:

• `1 <= s.length <= 10^4`
• `1 <= words.length <= 5000`
• `1 <= words[i].length <= 30`
• `s` and `words[i]` consist of lowercase English letters.

``````// Time Limit Exceeded
class Solution {
public:
vector<int> findSubstring(string s, vector<string>& words) {
if (s.empty() || words.empty()) return {};
vector<int> res;
int n = s.size(), cnt = words.size(), len = words[0].size();
unordered_map<string, int> wordCnt;
for (auto &word : words) ++wordCnt[word];
for (int i = 0; i <= n - cnt * len; ++i) {
unordered_map<string, int> strCnt;
int j = 0;
for (j = 0; j < cnt; ++j) {
string t = s.substr(i + j * len, len);
if (!wordCnt.count(t)) break;
++strCnt[t];
if (strCnt[t] > wordCnt[t]) break;
}
if (j == cnt) res.push_back(i);
}
return res;
}
};
``````

``````class Solution {
public:
vector<int> findSubstring(string s, vector<string>& words) {
if (s.empty() || words.empty()) return {};
vector<int> res;
int n = s.size(), cnt = words.size(), len = words[0].size();
unordered_map<string, int> wordMap;
for (string word : words) ++wordMap[word];
for (int i = 0; i < len; ++i) {
int left = i, curCnt = 0;
unordered_map<string, int> curMap;
for (int j = i; j <= n - len; j += len) {
string word = s.substr(j, len);
if (wordMap.count(word)) {
++curMap[word];
if (curMap[word] <= wordMap[word]) {
++curCnt;
} else {
while (curMap[word] > wordMap[word]) {
string t = s.substr(left, len);
--curMap[t];
if (curMap[t] < wordMap[t]) --curCnt;
left += len;
}
}
if (curCnt == cnt) {
res.push_back(left);
--curMap[s.substr(left, len)];
--curCnt;
left += len;
}
} else {
curMap.clear();
curCnt = 0;
left = j + len;
}
}
}
return res;
}
};
``````

Github 同步地址：

https://github.com/grandyang/leetcode/issues/30

Minimum Window Substring

https://leetcode.com/problems/substring-with-concatenation-of-all-words/

https://leetcode.com/problems/substring-with-concatenation-of-all-words/discuss/13656/An-O(N)-solution-with-detailed-explanation

https://leetcode.com/problems/substring-with-concatenation-of-all-words/discuss/13658/Easy-Two-Map-Solution-(C%2B%2BJava)

https://leetcode.com/problems/substring-with-concatenation-of-all-words/discuss/13664/Simple-Java-Solution-with-Two-Pointers-and-Map

LeetCode All in One 题目讲解汇总(持续更新中…)

（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，快快加入吧～）

|

Venmo 打赏

—|—

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation