DSA Longest Common Prefix

The problem

A prefix of a string is a string that sits at its very start. A common prefix of a list of words is a prefix shared by every word in the list. The task is to find the longest such prefix.

The answer can be empty. Words that disagree on the first letter share no prefix at all. A list with a single word answers with that whole word, because a word is its own prefix.

cases = [
    (["flower", "flow", "flight"], "fl"),
    (["inter", "internal", "internet"], "inter"),
    (["dog", "racecar", "car"], ""),
    (["alone"], "alone"),
]
for words, expected in cases:
    print(words, "longest common prefix:", repr(expected))

Read the first row column by column. All three words start with f, then l. The third letter splits them: o, o and i. The shared opening ends there, at fl.

Intuition

The first idea is to compare just two words. Find the common prefix of the first two words. Then assume it holds for the rest.

That assumption is the trap. The first two words can agree far beyond what the third word allows. Their shared prefix is only a candidate, and every later word can shrink it.

a = "flower"
b = "flow"
c = "flight"
prefix = ""
for x, y in zip(a, b):
    if x != y:
        break
    prefix += x
print("common prefix of first two:", repr(prefix))
print("third word starts with it:", c.startswith(prefix))

The candidate flow dies against flight. Shortening it letter by letter would eventually reach fl, which works. That shrinking process is exactly the brute force, and its cost depends on how many letters get tried and discarded.

Brute force: try every prefix of the shortest word

No common prefix can be longer than the shortest word. The straightforward method takes that shortest word and tries its prefixes from longest to shortest. The first prefix that every word starts with is the answer.

Trying a prefix means testing it against every word. A single failing word discards the prefix and moves to a shorter one. The empty prefix always succeeds, so the search always ends.

def lcp_brute(words):
    if not words:
        return "", 0
    shortest = min(words, key=len)
    checks = 0
    for length in range(len(shortest), -1, -1):
        candidate = shortest[:length]
        ok = True
        for word in words:
            checks += 1
            if not word.startswith(candidate):
                ok = False
                break
        if ok:
            return candidate, checks
    return "", checks

prefix, checks = lcp_brute(["flower", "flow", "flight"])
print("prefix:", repr(prefix))
print("startswith checks:", checks)

The answer is right. The waste is the discarded work. The full-length candidate flow is tested against all three words before it fails, and then flo is tested all over again from the first word. Each shorter candidate restarts the checking.

The optimal solution: scan column by column

Comparing one letter column across all words at a time, and stopping at the first column that disagrees, finds the prefix in a single outward scan. That is the whole solution.

Column 0 is the first letter of every word. Column 1 is the second letter, and so on. A column joins the prefix only when every word agrees in it. The scan also stops when a word runs out of letters, because no prefix can be longer than the shortest word.

def longest_common_prefix(words):
    if not words:
        return ""
    prefix = ""
    for col in range(len(words[0])):
        letter = words[0][col]
        for word in words[1:]:
            if col >= len(word) or word[col] != letter:
                return prefix
        prefix += letter
    return prefix

cases = [
    (["flower", "flow", "flight"], "fl"),
    (["inter", "internal", "internet"], "inter"),
    (["dog", "racecar", "car"], ""),
    (["alone"], "alone"),
]
for words, expected in cases:
    print(words, "->", repr(longest_common_prefix(words)), "expected", repr(expected))

All four cases from the start of the article pass. The dog row answers empty on the very first column. The scan returns the prefix built so far the moment anything disagrees, so no letter is ever rechecked.

Walkthrough

Follow flower, flow and flight through the columns. The prefix starts empty. Each column either extends it or ends the scan.

words = ["flower", "flow", "flight"]
prefix = ""
for col in range(len(words[0])):
    letters = [w[col] if col < len(w) else None for w in words]
    if all(ch == letters[0] for ch in letters):
        prefix += letters[0]
        print("column", col, "letters", letters, "all equal -> prefix:", repr(prefix))
    else:
        print("column", col, "letters", letters, "disagree -> stop, prefix:", repr(prefix))
        break

Column 0 holds f, f and f, so f joins the prefix. Column 1 holds l, l and l, so l joins too. Column 2 holds o, o and i.

That disagreement ends the scan. The prefix stays fl. Columns beyond 2 are never looked at, because no later agreement can repair an earlier split.

Complexity

The column scan takes O(c x w) time in the worst case, where c is the length of the shortest word and w is the number of words: it compares at most one full column per letter position. It takes O(1) extra space beyond the answer string it builds.

def brute_checks(words):
    shortest = min(words, key=len)
    checks = 0
    for length in range(len(shortest), -1, -1):
        candidate = shortest[:length]
        ok = True
        for word in words:
            if word is shortest:
                continue
            checks += 1
            if not word.startswith(candidate):
                ok = False
                break
        if ok:
            return checks
    return checks

def column_comparisons(words):
    compared = 0
    for col in range(len(words[0])):
        letter = words[0][col]
        for word in words[1:]:
            compared += 1
            if col >= len(word) or word[col] != letter:
                return compared
    return compared

for n in [4, 8, 16]:
    words = ["fl" + "x" * n, "fl" + "y" * n, "fl" + "z" * n]
    print("tail length", n, "brute checks:", brute_checks(words),
          "column comparisons:", column_comparisons(words))

These word families share only fl, but their shortest word is long. The brute force tries every longer prefix first and pays one failed check per discarded length, so its count grows with the tail. The column scan stops in column 2 and pays the same small count at every size.

Edge cases and pitfalls

An empty list has no first word to scan. The solution returns the empty string before any indexing happens. An empty word inside the list is just as decisive: it caps the prefix at length zero, because it has no letters to agree with.

Indexing past the end of a short word is the classic bug in this problem. The scan must test col >= len(word) before it tests word[col]. Python raises an IndexError otherwise, on exactly the inputs where a short word should end the scan quietly.

Comparing whole words pairwise and keeping the longer result is another trap. A common prefix must hold against every word at once. A prefix that survives two words can still die against the third, as the intuition section showed.

def longest_common_prefix(words):
    if not words:
        return ""
    prefix = ""
    for col in range(len(words[0])):
        letter = words[0][col]
        for word in words[1:]:
            if col >= len(word) or word[col] != letter:
                return prefix
        prefix += letter
    return prefix

tests = [[], ["", "abc"], ["abc", "abc"], ["ab", "a"], ["same", "same", "same"]]
for words in tests:
    print(words, "->", repr(longest_common_prefix(words)))

Identical words answer with the whole word. A word that is a prefix of another, like a beside ab, caps the answer at itself. Both behaviours fall out of the column scan with no special handling.