30\. Substring with Concatenation of All Words
# 30. Substring with Concatenation of All Words (opens new window)
# Description
Difficulty: Hard
Related Topics: Hash Table (opens new window), String (opens new window), Sliding Window (opens new window)
You are given a string s
and an array of strings words
of the same length. Return all starting indices of substring(s) in s
that is a concatenation of each word in words
exactly once, in any order, and without any intervening characters.
You can return the answer in any order.
Example 1:
Input: s = "barfoothefoobarman", words = ["foo","bar"]
Output: [0,9]
Explanation: Substrings starting at index 0 and 9 are "barfoo" and "foobar" respectively.
The output order does not matter, returning [9,0] is fine too.
1
2
3
4
2
3
4
Example 2:
Input: s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
Output: []
1
2
2
Example 3:
Input: s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
Output: [6,9,12]
1
2
2
Constraints:
- 1 <= s.length <= 104
s
consists of lower-case English letters.1 <= words.length <= 5000
1 <= words[i].length <= 30
words[i]
consists of lower-case English letters.
# Solution
Language: JavaScript
/**
* @param {string} s
* @param {string[]} words
* @return {number[]}
*
*/
var findSubstring = function(s, words) {
const [wordsCount, size] = [words.length, words[0].length];
const limit = s.length - wordsCount * size;
const map = {};
const ans = [];
words.forEach(word => map[word] ? map[word]++ : map[word] = 1);
for (let i = 0; i <= limit; i++) {
if (!map[s.slice(i, i + size)]) continue;
const seen = {};
let [j, count] = [i, 0];
while (count < wordsCount) {
const sub = s.slice(j, j + size);
seen[sub] ? seen[sub]++ : seen[sub] = 1;
if (!map[sub] || seen[sub] > map[sub]) break;
j += size;
count++;
}
if (count === wordsCount) ans.push(i);
}
return ans;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33