getSubstringStartIndex.js

const isObject = input => typeof input === 'object' && input !== null;

/**
* @returns {Object} An object literal representing a trie of strings
*/
function createTrie(strings = []) {
  return strings.reduce((trie, string) => {
    let pointer = trie;
    const chars = string.split('');

    chars.forEach((char, i) => {
      // A boolean value follows the last character of each word.
      // We'll use this to remember if a word was seen 
      const isLastCharacter = chars[i + 1] === undefined;
      
      if (isLastCharacter) {
        pointer[char] = false;
      } else {
        pointer[char] = {};
        pointer = pointer[char];
      }
    });
    return trie;
  }, {});
}

/*
* @desc Each branch of the trie ends with a bool indicating if the word
* was seen. This function resets all the bools to false. Because the size
* of a trie is confined by the character set, this operation takes O(1)
* time and O(1) space.
*/
function resetWordsSeenInTrie(trie = {}) {
  for (const char in trie) {
    if (typeof trie[char] === 'boolean') {
      trie[char] = false;
    } else if (isObject(trie[char])) {
      resetWordsSeenInTrie(trie[char]);
    }
  }
}

/**
* @returns {Number|null}
*/
function getSubstringStartIndex(words = [], text = '') {
  if (!Array.isArray(words) || typeof text !== 'string') {
    throw new TypeError('Invalid word list or corpus');
  }
  if (!words.length || !text.length) {
    return null;
  }

  // This is our "n"
  const totalWords = words.length;

  let trie = createTrie(words),
      totalWordsMatched = 0,
      matchStartIndex = null,
      pointer = trie;

  let i = 0;
  for (const char of text.split('')) {
    /* If this character exists in the top level of the trie,
    remember its index. This might be the start of a match. */
    if (char in pointer && !Number.isInteger(matchStartIndex)) {
      matchStartIndex = i;
      pointer = pointer[char];

    /* The character exists in the current level of the trie, but
    it does not mark the start of the potential substring. */
    } else if (char in pointer && isObject(pointer[char])) {
      pointer = pointer[char];

    /* This is the last character of a word, and we haven't seen the
    word since we set the matchStartIndex. */
    } else if (char in pointer && pointer[char] === false) {
      // Mark the word as seen and reset the pointer
      pointer[char] = true;
      totalWordsMatched+= 1;
      pointer = trie;

    /* If we encounter a word that we have seen since we started
    matchStartIndex - or a character that isn't in the trie - this
    isn't a valid match. Therefore, we need to reset. */
    } else  {
      matchStartIndex = null;
      pointer = trie;
      totalWordsMatched = 0;

      // Reset all the bools indicating if a word was seen
      resetWordsSeenInTrie(trie);
    }
    if (totalWordsMatched === totalWords) {
      return matchStartIndex;
    }
    i++;
  }
  return null;
}

const testList = ['fat','cat','rat','hat'];
const testString = 'A weird substring is fatcatrathat.';

console.assert(
  getSubstringStartIndex(testList, testString) === 20,
  'The function prints the starting index of a permutation of the test list'
);