DSAPrep
EasyStrings

Longest Common Prefix

Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string "".

Example 1

            Input: strs = ["flower","flow","flight"]
            Output: "fl"
            

            
                Explanation: "f" and "l" appear at the start of every string; the words diverge at index 2 (o, o, i), so the prefix stops at "fl".

Example 2

            Input: strs = ["dog","racecar","car"]
            Output: ""
            

            
                Explanation: There is no common prefix among the input strings — the first letters already differ (d, r, c).

Constraints

  • 1 <= strs.length <= 200
  • 0 <= strs[i].length <= 200
  • strs[i] consists of only lowercase English letters if it is non-empty.
View original on LeetCode ↗

Every string wears its prefix on its left edge: two words share a prefix exactly where their left edges read the same, character by character. So the question — longest common prefix of the whole array — is really how far left do all the rows agree? Line the words up at position 0 and the answer is the width of the agreed-on strip, nothing more. That reframing turns a pairwise problem into one straight left-to-right pass: compare position 0 across every word, then position 1, and stop the moment a column disagrees or a word runs out. Whatever was accepted before that moment is the answer.

Brute Force: Horizontal Pairwise Reduction

Time O(S·L)Space O(1)

Keep a running candidate and fold every word into it: after each fold the candidate is the longest prefix shared by everything folded in so far. The fold itself is the whole algorithm — walk the candidate and the next word from their left edges, count how far they agree, then slice the candidate down to that length. If a fold empties the candidate, no later word can revive it: a shared prefix must start the same way in every row, so the answer is the empty string.

class Solution:
    def longestCommonPrefix(self, strs: list[str]) -> str:
        prefix = strs[0]
        for s in strs[1:]:
            i = 0  # count how many leading characters agree
            while i < len(prefix) and i < len(s) and prefix[i] == s[i]:
                i += 1
            prefix = prefix[:i]
            if prefix == "":
                return ""
        return prefix

Why it is O(S·L) with S strings of length at most L: each fold walks the current candidate once, left to right, counting shared characters, and the candidate only ever shrinks — so the folds cost at most one character comparison per candidate character, bounded by L each. Space is O(1) apart from the answer: just the candidate and a counter. Each slice allocates a throwaway copy at most as long as the current candidate, but the only string that survives is the running prefix itself.

Optimal: Vertical Column Scan

OptimalTime O(S·L)Space O(1)

Same primitive — compare left-edge characters — different orientation. The horizontal fold compares every word against the running candidate. The vertical scan flips the loop: for each column index, take the first word’s character as the baseline and check it against every other word at that same position, before committing anything to the result. Survival is all-or-nothing per column: one bad row caps the prefix instantly, and a row that runs out of letters caps it too, via the i >= len(s) guard before the subscript is ever evaluated. The horizontal fold re-reads matched characters of each new word; the vertical scan reads each surviving character exactly once and exits the moment a column dies — no re-reading, no rebuilding, no shrinking.

class Solution:
    def longestCommonPrefix(self, strs: list[str]) -> str:
        result = ""
        for i in range(len(strs[0])):
            char = strs[0][i]
            for s in strs[1:]:
                if i >= len(s) or s[i] != char:
                    return result
            result += char
        return result

Watch the shared prefix grow on the textbook example: columns 0 and 1 turn emerald and donate their letters to the prefix card, then column 2 dies on flight’s i — the single mismatch that ends the whole scan:

start — 3 rows, scanning from column 0
strs[0]
f0l1o2w3e4r5
strs[1]
f0l1o2w3
strs[2]
f0l1i2g3h4t5
prefix
empty — nothing shared yet

columns are read top to bottom against the first row; one bad letter (or a row running out) caps the prefix for good

1 / 6
comparingresultdiscardedcurrent

The shared prefix is the left-edge stretch where every row agrees. Stack words as rows and read columns top to bottom with row 0 as baseline. A column survives only when all rows write the same letter; the first mismatch caps it.

Watch the fastest exit possible: the very first comparison disagrees, so the scan ends before a single letter reaches the prefix card:

start — 3 rows, scanning from column 0
strs[0]
d0o1g2
strs[1]
r0a1c2e3c4a5r6
strs[2]
c0a1r2
prefix
empty — nothing shared yet

columns are read top to bottom against the first row; one bad letter (or a row running out) caps the prefix for good

1 / 4
comparingresultdiscardedcurrent

Second example: dog, racecar, car. Same setup, one row per word, columns read top to bottom against the row 0 baseline. The scan can finish on the very first column, returning the empty string.

Why it is O(S·L) but better: the worst case is still O(S·L) — if every word is identical and L chars long, each of the S·L characters is compared once — so being honest, both solutions share the same complexity class. The vertical scan wins on the constants: every character is read at most once, matched characters are never re-examined or re-copied, and the scan exits at the first bad column (or the first word that ends). On the trace above the divergence at column 2 stops the work while most of the rows are still untouched. Space is O(1) beyond the returned string, which accumulates one accepted letter per round.