Searching a string for any permutation of words Given a string and an array of words, return all indexes in string for which a concatenation of all words in the array,
  in any order (so ["eensie", "weensy", "spider"] has six orderings) can be matched. All words will be the same length.


I am new to programming so please tell me where my big slow down points are. I still am failing the time test.

 var findSubstring = function(s, words) {
         var concatLength = 
         for (var i = 0; i &lt; words.length; i++){
         concatLength += words[i].length;
       } //concatLength is now length of all possible concatentations
       var stringLength = s.length;
       var answers = [];

       if (concatLength &gt; stringLength || concatLength === 0){
           return answers;
       }  //outlier cases where answer is inevitably an empty array
         var wordLength = words[0].length  //each word is the same length          
         var currentPerm;  //this will be used in permutation function we call
       for (var i = 0; i &lt; stringLength + 1 - concatLength; i++){ 
           try { //if a match is found in recursive permutations function, an object of type TrueValue is thrown up the stack
             wordsInString(words.slice(), -1, s.substr(i, concatLength));
           }
           catch(e){
               if (e.constructor === TrueValue)
                   answers.push(i);
               else
                  throw e;
           }

       }
       function TrueValue() { //constructor of instances to be thrown up stack in case of match
       }
       function wordsInString(words, index, string){ //permutations function
         if (index === -1)  //In each loop outside it is called with -1 as index, so we reset currentPerm to be empty
                    currentPerm = [];  
         if (words.length === 0){  //if currentPerm is full, check if it matches string.  If so throw instance of TrueValue up the stack
                   if (currentPerm.join("") === string)
                       throw new TrueValue();
               }
          for (var i = 0; i &lt; words.length; i++){
            if (string.substr(0,(currentPerm.length + 1) * wordLength) === currentPerm.join("") + words[i]){ //if what is already in currentPerm were to have this word concatenated onto it, would it be potential match of index of string we are currently on?  If so, move this word off of words array and onto currentPerm.  Continue to try all possible concatenations of words we have left via recursion
                     currentPerm.push(String(words.splice(i, 1)));
                     wordsInString(words, i, string);
                   }
               }
               if (index !== -1) //unless this is the first call to wordsInCurrentString, take last word of currentPerm off and move it back onto the place it was on in words before this particular call was made
                   words.splice(index, 0, currentPerm.pop());
               else 
                   return false;
           }
       return answers;
    };
OK, first of all, exceptions are slow. Any code that uses exceptions in the normal flow of the application will be slow. Only use exceptions for something that has gone terribly wrong in your application, never for the normal execution of your code.

Having said that, I approached the problem from a different angle. You have two tasks in essence: the first task is to generate all the permutations of the input array of words. The second task is, for every permutation of the words you calculate, concatenate them into a pattern string, and try to find that pattern in your input string wherever it may occur. Since these are two entirely separate tasks, isolate them in separate functions. The great thing about doing this is that you can test them separately and only use them in the overall solution when you know they work properly.

The second task is actually way simpler than the code you have, where you are continually chopping up the input string through substr(). You are missing the indexOf() function which just returns the index of the pattern in the string, or -1 if it was not found. Even better, the second parameter to indexOf() is the starting index for the search (with a default of 0).

Here's one way of doing that second task.

var findPermutation = function (permutation, s, result) {
  "use strict";
  var i, index,  
      pattern = permutation.join("");

  for (i = 0; i &lt; s.length - pattern.length; i += 1) {
    index = s.indexOf(pattern, i);
    if (index &gt;= 0) {
      result.push(index);
      i = index;
    }
  }
};

var result = [];
findPermutation(['a', 'b', 'c'], "abcabc", result);
console.log(result); // should be [0, 3]
findPermutation(['c', 'a', 'b'], "abcabc", result);
console.log(result); // should now be [0, 3, 2]


A few things to note here: permutation is some permutation of an array of words and so is itself an array. s is the string to search through, and result is an array of indexes that have been found. The for loop is cut short when the remaining bit of the string to search through is smaller than the pattern length. The code at the end is testing this simple routine (and if I'd written it properly, the test code would itself check that result has the right values. So, BOOM, we have the second part done; now all we have to do is generate the complete set of permutations from an array.

Here, I did it in a functional style: rather than have the routine generate, say, a huge array of all the permutations, I wrote the routine to accept a callback function and this will be called for every permutation that was generated (after which the permutation can be thrown away). In other words, the permutation generator would generate the next permutation, execute the callback function with this value, and then go back and calculate the next permutation. It would stop this merry-go-round once all the permutations had been generated.

For the permutation generator I went with Heap's Algorithm. It's the fastest, you can read up about it on wikipedia, and I'd already written about the algorithm and written a JavaScript version on my blog. Here's that code:

var generatePermutations = function (items, process) {
  "use strict";
  var generate = function (last, items, process) {
    var
      i,
      swap = function (x, y) {
        //console.log(x + " &lt;=&gt; " + y);
        var temp = items[x];
        items[x] = items[y];
        items[y] = temp;
      };

    //console.log(last);
    if (last === 0) {
      process(items);
    }
    else {
      // if last is even
      if ((last &amp; 1) !== 1) { 
        for (i = 0; i &lt; last; i += 1) {
          generate(last - 1, items, process);
          swap(0, last);
        }
      }
      // else last is odd
      else {
        for (i = 0; i &lt; last; i += 1) {
          generate(last - 1, items, process);
          swap(i, last);
        }
      }
      generate(last - 1, items, process);
    }
  };

  generate(items.length - 1, items, process);
};

generatePermutations(['a', 'b', 'c', 'd'], function (items) {
  console.log(items.join(""));
});


The last bit of the code shows how it is called: an array of items to be permuted and then a callback function that will be called for every permutation generated (all this one does is to merely output the items joined into a string).

If you are not familiar with this style of writing callback functions you can separate them out like this:

var callbackFunction = function (items) {
  console.log(items.join(""));
};
generatePermutations(['a', 'b', 'c', 'd'], callbackFunction);


So now we have it all: a permutation-of-words generator and a pattern matcher for each permutation of words. Since the callback function is so simple -- it only requires one parameter, yet the matcher requires three, I wrapped things up in another function:

var findPermutations = function (s, words) {
  "use strict";
  var result = [];

  generatePermutations(words, function (permutation) {
    var i, index,  
        pattern = permutation.join("");

    for (i = 0; i &lt; s.length - pattern.length; i += 1) {
      index = s.indexOf(pattern, i);
      if (index &gt;= 0) {
        result.push(index);
        i = index;
      }
    }
  });

  return result;
};

console.log(findPermutations("abcdabcd", ['a', 'b', 'c', 'd']));


Again I threw in a small test case at the end to check that everything worked. If you run it, it'll output [0, 4, 3, 2, 1] (with the matching patterns being abcd, abcd, dabc, cdab, bcda).

Aside: things that still aren't great. 


The permutation generator is a bit long-winded and can be rewritten to use some helper functions.
The permutation generator modifies the input array of words. It should make a copy, so that the original array is not changed.
I ignored the case where the length of the concatenated words is longer than the search string and hence nothing needs to be done. Easy exercise for the reader.