Longest common prefix

  • Code
  • JavaScript

Prompt

Write a function that takes a list of strings and returns the longest string that is a prefix of at least two strings in the list.

Example 1

Input: longestCommonPrefix(["flower", "flow", "flight"])

Output: "fl"

Example 2

Input: longestCommonPrefix(["dog", "racecar", "car"])

Output: ""

Example 3

Input: longestCommonPrefix(["interstellar", "internet", "internal", "interval"])

Output: "inter"

Approach: Vertical scan

The approach I took is to loop through the first item in the array, comparing each letter in that word to each letter within each of the remaining words in the array. This means I have two loops going, an outer loop over the first word, and an inner loop over each letter in each remaining word. This approach is called a Vertical scan. If the input is longestCommonPrefix(["flower", "flow", "flight"]), then you might visualize this like:

// first, outer loop["f", "l", "o", "w", "e", "r"]// second, inner loop[  ["f", "l", "o", "w"],  ["f", "l"]]

The edge cases I think are worth accounting for here:

  • If no array is provided or the provided array is empty, then an empty string, "" should be returned
  • If an array with only one item is provided, then the longest common prefix is just that string, so that single array item should be returned

Solution

Normally I would go through a hefty amount of detail walking through my solution, but in this instance, I think the more interesting thing is what I've missed and how I can improve. I'll dive into that in a bit, but here is my completed solution:

function longestCommonPrefix(array) {  if (!array || array.length === 0) {    return "";  }  if (array.length === 1) {    return array[0];  }
  const firstItem = array[0];  let commonPrefix = "";
  for (let i = 0; i < firstItem.length; i += 1) {    let j = 1;    while (j <= array.length - 1) {      if (j === array.length - 1 && firstItem[i] === array[j][i]) {        commonPrefix += firstItem[i];        j += 1;      } else if (firstItem[i] === array[j][i]) {        j += 1;      } else {        break;      }    }  }  return commonPrefix;}

To summarize, it loops through each letter in the first word, adding that letter to the commonPrefix string variable if that index has a match in every word in the array.

Big O of this solution

The time complexity of my solution is O(m * n), where n is the number of strings in array and m is the length of the shortest string in the array.

I only create one variable that gets returned and not garbage collected, commonPrefix, so there's a constant O(1) space complexity.

The downside to this approach

I've started running my solutions to these brainteasers by Google Gemini, asking it to check if my solution meets the requirements and to see how I might improve the solution. In this case, I did meet the requirements, but Gemini pointed out that my solution will keep looping through the first array item even after a mismatch has been found. This is definitely not good as the solution is doing more work than it needs to. Gemini offers the following as a refactored version of my solution that addresses this issue:

function longestCommonPrefixImproved(array) {  if (!array || array.length === 0) {    return "";  }
  if (array.length === 1) {    return array[0];  }
  const firstWord = array[0];  let commonPrefix = "";
  for (let i = 0; i < firstWord.length; i++) {    const char = firstWord[i];    for (let j = 1; j < array.length; j++) {      if (i === array[j].length || array[j][i] !== char) {        return commonPrefix;      }    }    commonPrefix += char;  }
  return commonPrefix;}

Alternate approach

While looking to Gemini to validate and improve on my solution is a fine place to leave things, I wanted to push things a little further and see if an entirely different and better approach was out there, so here was my follow-up prompt to Gemini:

What would be an alternative approach to this problem? Asked another way, how might a more senior software engineer at Google solve this problem? How is this solution better than mine?

Like just about everyone out there, I'm very new to AI and not totally sure how it will fit into my workflow. Setting aside many other valid questions and concerns on AI usage, I do think it's a good tool to figure out how better to approach these problems. In that spirit, I've shared my prompt above, and below is the solution it came up with from that prompt:

function longestCommonPrefixHorizontal(strs) {  if (!strs || strs.length === 0) {    return "";  }
  let prefix = strs[0]; // Start with the first string as the initial prefix
  for (let i = 1; i < strs.length; i++) {    while (strs[i].indexOf(prefix) !== 0) {      prefix = prefix.substring(0, prefix.length - 1);      if (prefix === "") {        return "";      }    }  }
  return prefix;}

While Gemini did offer an analysis of its solution, I think there's benefit in analyzing it myself to see how it works and how it might be better than mine.

Where my solution was a vertical scan, this solution is a horizontal scan. It works by assuming the first item in array is the longest common prefix. With that in mind, it iterates through the rest of the array, checking whether indexOf() the current prefix within the currently compared array item is not 0. If that's the case, then that means two things:

  1. the current prefix is not the actual longest common prefix
  2. the current prefix is too long and needs to be reduced.

So it drops one character off of prefix and restarts its search, continuing this pattern until the prefix becomes a prefix of the current string or becomes empty. When it finishes the loop, prefix (in its reduced state or as an empty string "") gets returned.

To my eyes there are two main benefits to this:

  1. It's a little more readable in certain places. The if (j === array.length - 1 && firstItem[i] === array[j][i]) comparison line specifically within my solution is a chore to wrap your head around.
  2. It's possibly more efficient. My solution starts with the assumption that the longest possible common prefix is a single character, then adds another character, then adds another character, and so on until we've reached the actual longest possible common prefix. Gemini's "more senior" approach assumes the longest possible common prefix is, well, a longer string and reduces down until the solution is hit. If the longest possible common prefix is actually longer, then the Gemini approach will reach that conclusion much more quickly than my approach would.