Longest Common Prefix — Solution

Problem

Given an array of strings, find the longest string that appears as a prefix of every string in the array. If no common prefix exists at all, return an empty string.

• Input: ["flower", "flow", "flight"]

• Output: "fl"

• Explanation: "fl" is the longest string that all three words start with.

• Input: ["dog", "racecar", "car"]

• Output: ""

• Explanation: There is no character shared at position 0 across all three words.

Intuition

The prefix must match every string simultaneously, so the moment any string disagrees — or runs out of characters — the prefix is done. Scan the array column by column (one character position at a time) and stop at the first mismatch. This naturally finds the answer in a single pass without any preprocessing.

Solution — Vertical Scanning

Check each character position across all strings. As soon as any string is too short to have a character at that position, or its character differs from the first string's, return everything accumulated so far.

1. Handle the empty array edge case immediately.
2. Iterate over character positions in strs[0] (the reference string).
3. For each position col, grab the character from strs[0].
4. Compare that character against every other string at the same position.
5. If any string is shorter than col + 1, or has a different character, return strs[0][:col].
6. If the outer loop completes without a mismatch, the entire first string is the common prefix.

1def longestCommonPrefix(strs: list[str]) -> str:
2    if not strs:
3        return ""
4
5    for col in range(len(strs[0])):
6        current_char = strs[0][col]
7        for row in range(1, len(strs)):
8            # Stop if this string ends before position col, or character differs
9            if col >= len(strs[row]) or strs[row][col] != current_char:
10                return strs[0][:col]
11
12    return strs[0]

Time: O(S) where S is the total number of characters across all strings — in the worst case every character is examined exactly once.

Space: O(1) extra space — the returned prefix is a slice of the existing first string.

Complexity Summary

Common Mistakes

• Accessing strs[row][col] without a bounds check — when a string is shorter than strs[0], this causes an index-out-of-bounds. The length guard col >= len(strs[row]) must come before the character comparison.
• Forgetting the empty input case — if strs is empty, strs[0] raises an exception immediately. Always return "" first.
• Sorting to compare only first and last — sorting alphabetically does make the shortest prefix appear between the lexicographic extremes, but adding O(n log n) sorting to an O(S) problem is pure overhead and easy to get wrong.
• Returning strs[0] as a special-case guess without understanding why — it's only correct because the outer loop runs exactly to len(strs[0]) and only exits early via return. If the loop finishes, strs[0] is indeed the LCP.
• Using a growing result string instead of a slice index — appending characters one by one is correct but obscures the natural slice: strs[0][:col] captures the prefix directly without construction.

Related Problems

• longest-substring-without-repeating-characters — character-level scanning over strings with early termination
• valid-anagram — verifying character-level equality between strings
• is-subsequence — two-pointer character matching across two strings
• find-the-index-of-the-first-occurrence-in-a-string — substring matching with character-by-character comparison
• longest-palindromic-substring — finding an optimal substring through systematic character comparisons