Longest Common Prefix

This is often asked as an easy opener, and the interviewer's real question is hidden: can you pick the simplest correct solution, and do you know when the heavier trie solution earns its place? The old advice holds — compare the trie with a plain column scan and say which you would ship.

The problem

Given a list of words, return the longest string that is a prefix of every word. If they share no first letter, return the empty string.

Example 1. ["interview", "internet", "interval", "internal"] → "inter". All four start with i-n-t-e-r; at the sixth letter they split into v and n.

Example 2. ["cat", "dog"] → "". The first letters already differ.

Constraints. 1 to 10,000 words, each 0 to 1,000 lowercase letters.

Clarifying questions

• Can the list be empty? Assume at least one word, but return "" for an empty list anyway.
• Can a word be empty? Yes — then the answer is "".
• Is the answer a prefix of the first word? Always: a common prefix is a prefix of every word, including the first.
• Case-sensitive? Yes; the input is lowercase.

Approach 1: the simple way

The answer is some prefix of the first word. Try them all, longest first, and return the first one that every word starts with.

1def lcp_brute(words: list[str]) -> str:2    """Try every prefix of the first word, longest first."""3    if not words:4        return ""5    first = words[0]6    for length in range(len(first), 0, -1):7        prefix = first[:length]8        if all(w.startswith(prefix) for w in words):9            return prefix10    return ""

For a first word of length L and n words, there are up to L candidate prefixes. Each check compares up to L characters with each of n words. That is O(n × L²) time.

Take the worst input: 9,999 identical words of 1,000 letters, then one last word that shares nothing. Every candidate length reads the first 9,999 words in full before the last word rejects it. That is about 10,000 × (1,000 + 999 + … + 1) ≈ 5 × 10^9 character comparisons. The waste is that the check for length 999 repeats almost all the work of the check for length 1,000.

The key insight

The common prefix can only get shorter as you read further. Once one word disagrees at position i, no longer prefix can be common — so there is nothing to gain from checking the long prefixes first.

Turn the search around. Read column by column: position 0 of every word, then position 1 of every word, and so on. The first column where some word differs, or some word runs out, ends the answer. Each character is read at most once, and the scan stops at the first mismatch.

Approach 2: vertical scan

1def lcp_vertical(words: list[str]) -> str:2    """Compare column by column; stop at the first mismatch."""3    if not words:4        return ""5    first = words[0]6    for i, ch in enumerate(first):7        for w in words[1:]:8            if i == len(w) or w[i] != ch:9                return first[:i]10    return first

Step by step:

1. Take each position i of the first word, with its character ch.
2. Check every other word at position i. If a word is too short (i == len(w)) or has a different character, the answer is first[:i].
3. If the loop finishes, every word starts with the whole first word, so the first word is the answer.

Dry run on ["interview", "internet", "interval", "internal"]:

The scan stops at the first mismatching word, so interval and internal are never read at position 5.

Complexity. Time O(S) in the worst case, where S is the total number of characters — more precisely O(n × m), where m is the answer's length plus one. Space O(1) beyond the output. With 10,000 words of 1,000 letters, that is at most 10^7 comparisons on any input. On the brute force's worst input above, the scan stops at column 0 after reading 10,000 characters.

Approach 3: a trie

Insert every word into a trie — the Trie class from the core-idea lesson. The common prefix is the path from the root that never branches: walk down while the current node has exactly one child and no word ends there.

1def lcp_trie(words: list[str]) -> str:2    """Insert every word, then walk down while the path does not branch."""3    if not words:4        return ""5    trie = Trie()6    for w in words:7        trie.insert(w)8    node, prefix = trie.root, []9    while len(node.children) == 1 and not node.is_word:10        ch, node = next(iter(node.children.items()))11        prefix.append(ch)12    return "".join(prefix)

The two stopping rules matter. Two or more children means the words split here. A flag means some word ends here — for ["ab", "abc"], the walk must stop at ab even though node b has one child, because ab cannot be extended.

On the example, the trie's path i → n → t → e → r has one child at each step, then node r has two children, v and n. The walk stops with "inter".

Complexity. Building costs O(S) time and O(S) space; the walk costs O(m). So the trie is never faster than the vertical scan for a single list — it reads every character, while the scan stops at the first mismatch — and it uses far more memory.

Which would you ship? The vertical scan. The trie earns its place only when the same word list answers many questions. If the interviewer asks "now, for each of 10,000 incoming query strings, return its longest common prefix with the dictionary", build the trie once and answer each query in O(length of the query).

Edge cases

• One word → the word itself. The inner loop has nothing to compare against, so the outer loop finishes.
• An empty word anywhere → "". In the scan, i == len(w) is true at i = 0. In the trie, the root's flag is set, so the walk never starts.
• One word is a prefix of another (["ab", "abc", "abcd"]) → "ab". The short word runs out first; the length check catches it.
• No shared first letter → "" at i = 0.

Follow-ups

• "Sort first?" The common prefix of the whole list equals the common prefix of the alphabetically smallest and largest words, because every other word sorts between them. Comparing min(words) and max(words) takes O(S) time and O(1) extra space, with no sort needed.
• "Many queries against one dictionary." Build the trie once, then walk each query as far as it matches: O(length of the query) each.
• "Longest prefix shared by at least k words." Store a count on each trie node; the answer is the deepest node whose count is at least k.