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

Example 2:

Input: s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
Output: []
1
2

Example 3:

Input: s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
Output: [6,9,12]
1
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
上次更新: 2022/7/14 下午7:06:25