LeetCode 14 – Longest Common Prefix

Longest Common Prefix is a five-minute problem whose only real content is the edge cases. The solution everybody writes first compares strings horizontally — prefix of the first two, then that against the third — and it works. Scanning vertically instead is shorter, exits earlier, and makes the empty-string case disappear.

The problem

Given an array of strings, return the longest string that is a prefix of every one of them. If there is no common prefix, return "".

["flower", "flow", "flight"]  -> "fl"
["dog", "racecar", "car"]     -> ""      nothing in common
["interspecies", "interstellar", "interstate"] -> "inters"
["a"]                         -> "a"     one string is its own prefix
["ab", ""]                    -> ""      an empty string kills any prefix

Vertical, not horizontal

The horizontal approach walks the array carrying a running prefix and shrinking it. The vertical approach fixes a character position and checks it down the whole array before moving right:

          i=0  i=1  i=2
flower     f    l    o
flow       f    l    o
flight     f    l    i   ← mismatch at i = 2, answer is "fl"

Two things fall out of that. It stops at the first mismatched column, so ["a", "zzzzzzzz..."] costs one comparison rather than a scan of the long string. And the answer is always a prefix of strs[0], so you never build up a result — you slice the first string at the column where it broke.

The bounds check is the part to get right. A string shorter than the current column is the answer's ceiling: for ["flow", "flower"], position 4 does not exist in "flow", and that ends the scan. Test i == s.length() before you index, in the same condition as the character comparison, and both the short-string case and the empty-string case are handled by one line.

Java

class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }

        String first = strs[0];
        for (int i = 0; i < first.length(); i++) {
            char c = first.charAt(i);

            for (String s : strs) {
                // Running off the end of a shorter string ends the prefix,
                // and checking it here keeps charAt in bounds.
                if (i == s.length() || s.charAt(i) != c) {
                    return first.substring(0, i);
                }
            }
        }

        return first;   // every string starts with all of strs[0]
    }
}

The inner loop starts at strs[0] rather than strs[1]. Comparing the first string against itself is one wasted comparison per column and it buys a loop with no index arithmetic — worth it.

Python

class Solution:
    def longestCommonPrefix(self, strs: list[str]) -> str:
        if not strs:
            return ""

        first = strs[0]
        for i, c in enumerate(first):
            for s in strs:
                if i == len(s) or s[i] != c:
                    return first[:i]

        return first

Python has os.path.commonprefix(strs), which solves this exactly — including returning "" for an empty list. It is worth knowing and it is not the answer to give; the interviewer wants the loop.

The sorting trick

Sort the array and you only need to compare the first and last strings. Anything lexicographically between them must share whatever prefix those two share:

Arrays.sort(strs);
String head = strs[0], tail = strs[strs.length - 1];

int i = 0;
while (i < head.length() && i < tail.length() && head.charAt(i) == tail.charAt(i)) {
    i++;
}
return head.substring(0, i);

It is a genuinely nice observation and it is the worse answer here: sorting costs O(n·m log n) where the vertical scan costs O(n·m), and it reorders the caller's array as a side effect. Offer it as an aside, not as the solution.

Complexity

The worst case for the vertical scan is every string being identical, where it reads all S characters. The best case is a mismatch in column 0, which is O(n) — and that early exit is what the horizontal version gives up.

What the interviewer is checking

• The empty array. strs[0] on an empty input throws, and it is the first thing tested.
• A string shorter than the emerging prefix — ["flow", "flower"].
• An empty string in the array, which forces "" no matter what else is there.
• That you never index past the end of a string.
• That you return early rather than scanning columns you already know are pointless.