Longest Common Prefix

Problem

Given a list of strings strs, return the longest string that is a prefix of every string in the list. If the strings share no leading characters at all, return the empty string "".

Examples

• Input: strs = ["flower", "flow", "flight"] → Output: "fl" All three start with "fl"; they disagree at the third character (o vs i).
• Input: strs = ["dog", "racecar", "car"] → Output: "" There is no character that all three strings start with.
• Input: strs = ["interspecies", "interstellar", "interstate"] → Output: "inters" All share "inters"; the next characters are p, t, t — not unanimous.

Constraints

• 1 <= len(strs) <= 200
• 0 <= len(strs[i]) <= 200
• Strings consist of lowercase English letters (possibly empty)

With S = total characters across all strings, O(S) is the target; anything polynomial passes at these sizes.

Think about it first

TL;DR

Vertical (column-by-column) scanning — O(S) time where S is the total number of characters, O(1) extra space.

Approach 1 — Brute force: test every prefix length

Any common prefix is a prefix of the first string. So try prefixes of the first string from longest to shortest and return the first one every other string starts with.

from typing import List


def longestCommonPrefix(strs: List[str]) -> str:
    first = strs[0]
    for k in range(len(first), -1, -1):
        candidate = first[:k]
        if all(s.startswith(candidate) for s in strs):
            return candidate
    return ""

Complexity: O(m² · n) time in the worst case (m = length of the first string, n = number of strings) — each startswith is O(m) and we may try m prefix lengths. O(m) space for the slices.

At 200×200 this still passes, but it rechecks the same leading characters over and over — the mismatch position can be found in a single coordinated pass.

Approach 2 — Vertical scanning

The insight: the strings agree on a prefix of length i+1 exactly when they agree on columns 0..i. So compare one column at a time and stop at the first column where any string disagrees or ends.

from typing import List


def longestCommonPrefix(strs: List[str]) -> str:
    first = strs[0]
    for i in range(len(first)):
        ch = first[i]
        for s in strs[1:]:
            if i >= len(s) or s[i] != ch:
                return first[:i]
    return first

Walkthrough on strs = ["flower", "flow", "flight"]:

1. Column 0: ch = 'f' — "flow" and "flight" both have f. Continue.
2. Column 1: ch = 'l' — both others have l. Continue.
3. Column 2: ch = 'o' — "flow" has o, but "flight" has i → mismatch.
4. Return first[:2] = "fl". Matches the expected output.

Complexity: O(S) time worst case (S = sum of all string lengths), but it stops at the first mismatch, so the best case is O(n) after one column. O(1) extra space.

Approach 3 — Horizontal scanning (fold)

The insight: LCP is associative — LCP(a, b, c) = LCP(LCP(a, b), c). Keep a running prefix and shrink it against each new string; if it ever becomes empty, stop early.

from typing import List


def longestCommonPrefix(strs: List[str]) -> str:
    prefix = strs[0]
    for s in strs[1:]:
        while not s.startswith(prefix):
            prefix = prefix[:-1]
            if not prefix:
                return ""
    return prefix

Walkthrough on ["flower", "flow", "flight"]: prefix = "flower"; against "flow" it shrinks "flower" → "flowe" → "flow"; against "flight" it shrinks "flow" → "flo" → "fl", which "flight" starts with. Return "fl".

Complexity: O(S) time, O(m) space for the running prefix.

Approach 4 — Sort trick: compare only the extremes

The insight: under lexicographic order, the two most different strings are the smallest and the largest. Any character shared by min(strs) and max(strs) is shared by everything ordered between them, so the LCP of the whole list equals the LCP of just those two strings.

from typing import List


def longestCommonPrefix(strs: List[str]) -> str:
    lo, hi = min(strs), max(strs)
    for i in range(len(lo)):
        if lo[i] != hi[i]:
            return lo[:i]
    return lo

Complexity: O(S) time to find the min and max, then O(m) for one pairwise comparison; O(1) extra space. The asymptotics match vertical scanning.

Common pitfalls

• Forgetting that a string may end before the current column — check i >= len(s) before reading s[i], or "flow" vs "flower" throws an IndexError instead of returning "flow".
• Returning None or crashing on a list containing an empty string — the answer is simply "".
• In the horizontal fold, keep the if not prefix: return "" early-out. It ends the scan on disjoint inputs like ["dog", "racecar"] instead of continuing to shrink an already-empty prefix.

Pattern takeaway

When comparing many sequences positionally, think in columns, not rows: advance a single index while all sequences agree, and stop at the first disagreement. A second idea is the reduction to extremes — if a property is preserved under an ordering (here, lexicographic min/max bracketing every string’s prefix), you may only need to examine the two boundary elements.