Substring with Concatenation of All Words

A concatenated string is a string that exactly 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 string because it is not the concatenation of any permutation of words.

Return an array of 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:

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.

Example 2:

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

Output: []

Explanation:

There is no concatenated substring.

Example 3:

Input: s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]

Output: [6,9,12]

Solution

/**

* @param {string} s

* @param {string[]} words

* @return {number[]}

const findSubstring = (s, words) => {

if (!words || words.length === 0) return [];

const m = words.length,

n = words[0].length,

len = m * n,

result = [];

const map = {};

for (word of words) map[word] = ~~map[word] + 1;

for (let i = 0; i < s.length - len + 1; i++) {

const temp = Object.assign({}, map);

for (let j = i; j < i + len; j += n) {

const str = s.substr(j, n);

if (!(str in temp)) break;

if (--temp[str] === 0) delete temp[str];

}

if (Object.keys(temp).length === 0) result.push(i);

}

return result;

};

Comments