Longest common sub string in a set of strings JavaScript

Question

I was trying to find longest common substring in a set of strings in JavaScript.

I got the idea from Find the longest common starting substring in a set of strings

but I am not only looking for staring sub string

So, I went ahead with following:

I guess it works as expected but there is an overhead of map and sort.

function longestCommonSubstring(array) {
    // Copy the array
    let arr = array.slice().sort();
    // For each individual string sort them 
    arr = arr.map(a => a.split('').sort().join(''));
    // Check the first and last string and check till chars match
    let a0 = arr[0],
        aLast = arr[arr.length -1],
        len = arr[0].length,
        i = 0;
    while(i < len && a0[i] === aLast[i]) i++;
    // return
    return a0.substring(0,i);
}

Am I doing any wrong? Can it be done in much more efficient way ?

INPUT ["abc","cxabgi"]

OUTPUT ["ab"]

I'm confused about `arr = arr.map(a => a.split('').sort().join(''));`, if you sort each input string lexiographically, you've lost the original order, which will make it impossible to determine what a matching substring would be. Your current code results in 'abc', not 'ab'. — CertainPerformance, Dec 26 '18 at 07:24
@CertainPerformance Ok yes. My bad :( So how to approach the problem then ? — StrugglingCoder, Dec 26 '18 at 07:26
I’m struggling to see how your question differs from the linked one, or any of those in its related list, like https://stackoverflow.com/q/10355103/215552 — Heretic Monkey, Dec 26 '18 at 07:29

score 0 · Answer 1 · answered Feb 15 '21 at 18:25

function longestCommonSubstring(array) {
  const sortedArray = [...array].sort();
  const firstItem = sortedArray[0];
  const lastItem = sortedArray[sortedArray.length - 1];
  const firstItemLength = firstItem.length;
  let i = 0;

  while (i < firstItemLength && firstItem.charAt(i) === lastItem.charAt(i)) {
    i++;
  }

  return firstItem.substring(0, i);
}

Longest common sub string in a set of strings JavaScript

1 Answers1