Longest Common Prefix

What the problem is really asking

We need the longest starting part that every string shares.

If even one string breaks the match, the prefix must be shortened.

Intuition

The first string is a natural starting guess.

Then each new string can only keep the prefix the same size or make it shorter. It can never make it longer.

Brute-force idea

One way is to compare characters column by column across all strings.

That works, but another very simple viewpoint is often easier to code:

• keep a candidate prefix
• shrink it until the current string starts with it

Optimized approach

Start with prefix = strs[0].

For every later string:

1. check whether the string starts with prefix
2. if not, remove the last character from prefix
3. repeat until it matches

When all strings agree, prefix is the answer.

class Solution {
    public String longestCommonPrefix(String[] strs) {
        String prefix = strs[0];

        for (int i = 1; i < strs.length; i++) {
            while (!strs[i].startsWith(prefix)) {
                prefix = prefix.substring(0, prefix.length() - 1);
            }
        }

        return prefix;
    }
}

Dry run

Take ["flower", "flow", "flight"].

• start with "flower"
• compare with "flow" -> shrink to "flow"
• compare with "flight" -> "flow" fails, then "flo" fails, then "fl" works

Answer: "fl".

Common mistakes

1. Forgetting that the answer can be empty

If the strings share nothing at the start, return "".

2. Comparing full strings every time

You only care about the prefix, not full equality.

3. Overusing a trie

A trie is possible, but this problem is usually solved more simply.

Complexity

Time Complexity: O(total characters checked)

Space Complexity: O(1) extra, ignoring the returned string