Longest Common Prefix

Longest Common Prefix asks for the longest run of leading characters shared by an entire list of words. It is a gentle string problem with one clean insight: instead of comparing the words against one another, line them up and compare them column by column, stopping the instant they disagree.

The slow way first

A tempting first idea is to fold the words together pairwise: take the common prefix of the first two, then combine that result with the third, and so on. It works, but it is fiddly and wasteful — you keep re-walking characters you already agreed on, and you carry a shrinking answer around.

The question to ask: where is the earliest place these words can possibly split apart? That place is a single column — one character position. So if we scan the positions left to right, the shared prefix ends exactly at the first column where the words stop agreeing.

The idea: scan vertically, stop at the first mismatch

Picture the words stacked in a grid, one per row. Read down each column: column 0 holds every word's first character, column 1 holds every word's second character, and so on. Treat the first word as a yardstick. At column j its character is ch; check that every other word also has ch at column j.

The moment a word either runs out of characters or shows a different character, the common prefix is everything to the left of that column.

The key insight: we never compare two whole words. We ask only one question per column — does everyone agree here? — and the first "no" hands us the answer immediately.

Walk through it

Step through the animation. The pointer j slides across the columns. Column 0 is all "d" and column 1 is all "e", so the prefix grows to "de". At column 2 the first word says "v" and develop agrees, but destiny says "s" — the first mismatch. We stop and return everything before column 2, which is "de".

Pseudocode

if the list is empty: return ""
first = words[0]                      # use the first word as the yardstick
for each column j in first:
    ch = first[j]
    for each other word w:
        if w is too short OR w[j] != ch:
            return first[:j]          # first disagreement -> stop
return first                          # every column agreed -> first is the prefix

The Python solution

def longest_common_prefix(words):
    if not words:
        return ""
    first = words[0]
    for j in range(len(first)):
        ch = first[j]
        for w in words[1:]:
            if j >= len(w) or w[j] != ch:
                return first[:j]
    return first

• The if not words guard handles the empty-list case up front.
• first = words[0] is the yardstick; we only ever check the others against it.
• The outer loop walks columns j; ch = first[j] is the character every word must share.
• The inner loop checks each remaining word w at that same column.
• Line 8 is the stop condition: a word is either too short (j >= len(w)) or its character differs (w[j] != ch).
• Line 9 returns first[:j] — everything to the left of the first disagreement.
• If no column ever disagrees, the whole first word is the prefix, so we return first.

Complexity

Here n is the number of words and m is the length of the shortest word; k is the length of the common prefix. We do constant extra work — just one slice at the end — so the space is O(1) beyond the output.

When this pattern shows up

Practice