# 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<arr.length; i++) {
for (var j=0; j<arr.length; j++) {
if (i !== j && (arr[i].indexOf(arr[j]) > -1 || arr[j].indexOf(arr[i]) > -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?

• I'm not sure I'm clear on the requirements. Does every element in the returned array need to be a substring or superstring of every other element in the array, or just of at least one other element in the array? – Thriggle Nov 23 '16 at 16:09
• every element of the array need not to be a substring or superstring of other elements but at lest one element of the array – Mr.7 Nov 24 '16 at 8:20
• What should be output when array contains more than one related strings e.g. ['abc', 'abcd', 'abcde', 'xyz', 'wxyz', 'vwxyz']? – Tushar Mar 30 '17 at 3:22
• @Thriggle I agree, the requirements are too vague. And a single example is insufficient to clarify the problem statement... – Igor Soloydenko May 24 '18 at 4:57

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) => a.length - b.length);

for (i = 0; i < list.length - 1; i++) {
match = [];
rest = [];
for (j = i; j < list.length; j++) {
if (list[j].indexOf(list[i]) > -1) {
match.push(list[j]);
} else {
rest.push(list[j]);
}
}
//Did we find a set?
if (match.length > 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));

One quick improvement you can do is to initialize inner for loop variable from
j = i+1 instead of j = 0 and you won't need to check i !== j

for (var j=i+1; j<arr.length; j++)
if (arr[i].indexOf(arr[j]) > -1 || arr[j].indexOf(arr[i]) > -1)
• Unfortunately, this change also changes the output of the algorithm. Example: for input ["abc", "ab"] you return ["abc"] while OP returns ["abc", "ab"]. – le_m Apr 28 '17 at 23:44
• Indeed, you assume probably a sorted array? – konijn Jun 27 '17 at 22:39