Longest Common Prefix

Find the longest common prefix for a list of strings.

const longestCommonPrefix = (arr) => {
  if (!arr || !arr.length) {
    return;
  }

  let low = 0;
  let high = arr[0].length - 1;

  for (const str of arr) {
    high = Math.min(str.length - 1, high);
  }

  let str = '';

  while (low <= high) {
    const mid = low + Math.floor((high - low) / 2);
    if (hasPrefix(arr, low, mid)) {
      str += arr[0].substring(low, mid + 1);
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }

  return str;
};

const hasPrefix = (arr, low, mid) => {
  const prefix = arr[0].substring(low, mid + 1);

  for (const str of arr) {
    if (!str.substring(low, mid + 1).startsWith(prefix)) {
      return false;
    }
  }

  return true;
};

console.log(longestCommonPrefix(['johnSmith', 'johnWick', 'john1'])); // 'john'
console.log(longestCommonPrefix(['jo1hnSmith', 'johnWick', 'john1'])); // 'jo'
console.log(longestCommonPrefix(['Smith', 'Wick', 'red'])); // ''

Demo

Runtime complexity: m*log(n)

m = length of the smallest string in the list.

n = length of the list.