Longest Common Prefix

Given a list of strings strs, return the longest string that every element of the list starts with. If the strings share no common starting characters, return the empty string "".

A prefix must match from the very first character: "inter" is a common prefix of "interview" and "internet", but a shared piece in the middle of the words does not count. The list may contain empty strings, and a single-element list's answer is that element itself.

Example 1

Example 2

Example 3

Constraints

• 1 <= strs.length <= 200
• 0 <= strs[i].length <= 200
• strs[i] contains only lowercase English letters.

Pattern Path · Math, Bits & Strings · problem 31 of 169

Start simple

Take each prefix of the first string, longest first, and test whether every string starts with it: O(L² · n) time for strings of length L.

The key idea

Use vertical scanning: compare the strings column by column. Take the first string as a reference. For each position i in it, check that every other string also has a character at position i and that the character matches. The first time either check fails, the common prefix is exactly the first i characters of the reference. If we get through the whole reference string, it is itself the answer.

This is correct because a prefix is common only if every column up to its length matches in every string, and as soon as one column fails, no longer prefix can work.

The work is at most n · m character comparisons, where m is the length of the answer plus one, and scanning stops early as soon as a mismatch appears, so lists whose strings diverge early are cheap even when the strings are long.

Complexity

• Time: O(S) where S is the total number of characters
• Space: O(1) extra

Python

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        first = strs[0]
        for i, ch in enumerate(first):
            for other in strs[1:]:
                # stop at the first column where some string ends or differs
                if i == len(other) or other[i] != ch:
                    return first[:i]
        return first

JavaScript

var longestCommonPrefix = function(strs) {
  const first = strs[0];
  for (let i = 0; i < first.length; i++) {
    for (let k = 1; k < strs.length; k++) {
      // stop at the first column where some string ends or differs
      if (i === strs[k].length || strs[k][i] !== first[i]) return first.slice(0, i);
    }
  }
  return first;
};

What the interviewer is checking

It is a quick check of clean string iteration and boundary handling: empty strings, a single string, and strings shorter than the reference.

Mistakes to avoid

• Indexing past the end of a shorter string.
• Forgetting that an empty string anywhere in the list forces the answer to be "".
• Comparing only the first two strings instead of all of them.

Follow-ups to expect

• Can you do it by sorting? (Compare only the first and last strings.)
• Many queries against a fixed word list? (Build a trie once.)
• Can binary search on the prefix length help? (Check candidate lengths in O(S).)

In real software

Shells and IDEs use it for tab completion of a shared prefix, and routers or file systems compute common prefixes when grouping IP routes or paths.

Practice next