Longest Common Prefix
Find the shared leading characters across an array of strings by shrinking a candidate prefix
Problem Statement
Write a function to find the longest common prefix shared by all strings in an array. If there is no common prefix, return the empty string "".
Input: ["flower", "flow", "flight"]
Output: "fl"
Input: ["dog", "racecar", "car"]
Output: ""Intuition
The key insight
The common prefix can only ever shrink. Start with a candidate and cut it down whenever a string disagrees — it never needs to grow back.
Two shapes follow from this:
Horizontal scanning — take the first string as the candidate, then shorten it against each subsequent string.
Vertical scanning — compare character position 0 across every string, then position 1, and so on. Stop at the first column where they disagree.
Vertical scanning is usually faster in practice because it stops at the first mismatched column, and the answer is bounded by the shortest string.
The upper bound
The prefix can never be longer than the shortest string in the array. ["ab", "abcdef"] is capped at length 2 no matter how similar the rest is. Vertical scanning gets this for free — it stops the moment any string runs out of characters.
Watch it run
Approach
Handle the empty input
An empty array has no common prefix — return "".
Walk the characters of the first string by index
The first string is a valid upper bound for the prefix.
For each column, check every other string
Stop if any string is shorter than the current index, or if its character differs.
Solution
def longest_common_prefix(strs: list[str]) -> str:
"""Longest prefix shared by every string, or '' if there is none."""
if not strs:
return ""
first = strs[0]
for i, char in enumerate(first):
for other in strs[1:]:
# Either this string ended, or it disagrees at column i.
if i >= len(other) or other[i] != char:
return first[:i]
return first # the first string is itself the common prefixThe horizontal-scanning version, which some find more intuitive:
def longest_common_prefix_horizontal(strs: list[str]) -> str:
if not strs:
return ""
prefix = strs[0]
for word in strs[1:]:
while not word.startswith(prefix):
prefix = prefix[:-1] # chop one character off the end
if not prefix:
return ""
return prefixA neat sorting shortcut
Sort the array lexicographically and compare only the first and last strings. Everything in between must share whatever prefix those two extremes share, because sorting places the most dissimilar strings at the ends.
It is elegant, but O(n × m log n) because of the sort — slower than the O(n × m) scan. Worth knowing as a party trick, not as the answer.
Complexity Analysis
Time Complexity
O(n × m)
Space Complexity
O(1)
Where n is the number of strings and m is the length of the shortest one.
- Time — in the worst case (all strings identical) every character of every string is compared. In practice the scan usually stops after a few columns.
- Space —
O(1)extra, ignoring the returned slice.
Edge Cases
Related Problems
- Find the Index of the First Occurrence in a String — character-by-character matching
- Isomorphic Strings — comparing strings position by position
- Group Anagrams — grouping strings by a shared property