30. Substring with Concatenation of All Words.md

30. Substring with Concatenation of All Words

• Difficulty: Hard.
• Related Topics: Hash Table, Two Pointers, String.
• Similar Questions: Minimum Window Substring.

Problem

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 = "wordgoodstudentgoodword",
  words = ["word","student"]
Output: []

Solution

/**
 * @param {string} s
 * @param {string[]} words
 * @return {number[]}
 */
var findSubstring = function(s, words) {
  var sLen = s.length;
  var wLen = words.length;
  var wordLen = (words[0] || '').length;
  
  if (!sLen || !wLen || !wordLen) return [];
  
  var count = 0;
  var tmp = '';
  var map1 = {};
  var map2 = {};
  var res = [];
  
  for (var i = 0; i < wLen; i++) {
    map1[words[i]] = (map1[words[i]] || 0) + 1;
  }
  
  out: for (var j = 0; j <= sLen - (wLen * wordLen); j++) {
    map2 = {};
    count = 0;
    while (count < wLen) {
      tmp = s.substr(j + (count * wordLen), wordLen);
      if (map1[tmp] === undefined || map1[tmp] === map2[tmp]) continue out;
      map2[tmp] = (map2[tmp] || 0) + 1;
      count++;
    }
    res.push(j);
  }
  
  return res;
};

Explain:

nope.

Complexity:

• Time complexity : O(m*n).
• Space complexity : O(m).