Finding substrings within arrays I need to find the substrings within my array. If I have an array: ["abc", "abcd", "abcde", "xyz"], my method should return the array members: abc, abcd, abcde as each is a substring or a superstring of the other, but it should exclude "xyz" as it is not related to other strings in any way.

function find_substrings(arr) {
    var res = [];
    for (var i=0; i&lt;arr.length; i++) {
        for (var j=0; j&lt;arr.length; j++) {
            if (i !== j &amp;&amp; (arr[i].indexOf(arr[j]) &gt; -1 || arr[j].indexOf(arr[i]) &gt; -1)) {
                res.push(arr[i]);
                break;
            }
        }
    }
    return res;
}
var arr = ["abc", "abcd", "abcde", "xyz"];
console.log(find_substrings(arr));


Here my code is of \$O(n^2)\$ complexity, as it's iterating twice over the complete array. Is there any optimal solution?
Interesting question,


find_substrings should really be findSubstrings
I dislike arr, and prefer list
If you sort the array by the length of strings, then you never have to check prior elements
If you kept a list of matches and non-matches, then you would never have to check matches again 
I found the test case troubling, since you are looking for only 1 set, whereas the code will retrieve any number of sets
The complexity calculation becomes tricky here, I would think a worst case would be n*n/2, and best case n.


In the end, I came up with something like this:



function findSubstrings(list) {
  var out = [],
    match, rest, i, j;
  //Sort the array by the length of the string
  list.sort((a, b) =&gt; a.length - b.length);

  for (i = 0; i &lt; list.length - 1; i++) {
    match = [];
    rest = [];
    for (j = i; j &lt; list.length; j++) {
      if (list[j].indexOf(list[i]) &gt; -1) {
        match.push(list[j]);
      } else {
        rest.push(list[j]);
      }
    }
    //Did we find a set?
    if (match.length &gt; 1) {
      out = out.concat(match);
      list = rest;
      i = 0;
      //Shortcut, should we still bother looking?
      if (rest.length == 0 || rest.length == 1) {
        return out;
      }
    }
  }
  return out;
}
var testCase = ["abc", "abcd", "abcde", "xyz", "tom", "tomd"];
console.log(findSubstrings(testCase));