vizlearn

Longest common prefix

Interview QuestionsBy Updated

Take the first word as a candidate prefix and shrink it against each following word. The prefix only ever gets shorter, so one pass settles it — O(n·m) in the worst case, and it exits early the moment the prefix is empty.

Overview

The shrinking candidate

The answer is a prefix of every string, so it is certainly a prefix of the first one. Start there and remove characters as each new word disagrees. Because it only shrinks, no backtracking is possible and one pass is enough.

Two bounds to state: the answer is at most the length of the shortest string, and the total work is O(sum of all characters) in the worst case — usually far less, because the candidate collapses quickly on real input.

StringsCoding problemEasy

Step through it

What to watch

  • The prefix shrinks and never grows.
  • Comparison stops at the length of the shorter of the two.
  • An empty prefix ends it immediately — nothing later can help.

Say this out loud

"Start with the first string as the candidate and trim it against each of the others. It can only shrink, so one pass is enough - O(total characters), and it stops early on an empty prefix."

Longest common prefix

Find the longest common prefix of a list of strings.

The sorting trick

Sort the list and compare only the first and last strings. In lexicographic order those two are the most different, so their common prefix is the whole list's. It is O(n log n·m) — worse asymptotically, and a nice observation to offer as an alternative rather than as the answer.

Vertical scanning, and tries

The other framing compares column by column: check index 0 across every word, then index 1, stopping at the first disagreement. Same complexity, and it exits earlier when the prefix is short and the strings are long.

If the question becomes "answer this repeatedly for many queries", the answer is a trie: insert every word, then walk down from the root while each node has exactly one child and ends no word. That is the structure this question is a warm-up for.

Run it in Python

Three approaches on the same input with their character comparisons counted, so "horizontal versus vertical" is a measurement rather than a preference.

common_prefix.pyPython 3
Output
How the code works
  1. prefix = prefix[:keep]The candidate can only shrink, which is what rules out any need to backtrack. Each word is examined once.
  2. if not prefix: breakOnce empty, nothing later in the list can extend it. On input with no shared first letter this turns the whole thing into one comparison.
  3. keep < len(prefix) and keep < len(w)Both bounds are needed. The answer is capped by the shortest string, and dropping either check indexes past the end of one of them.
  4. lo, hi = min(words), max(words)The sorting trick: in lexicographic order the extremes are the most different, so their shared prefix is the whole list's. Asymptotically worse, and a good thing to offer as an aside.
Change one thing
  • Make the first word the longest and the last word a single character. Vertical scanning wins comfortably.
  • Return the prefix length instead of the string to avoid the slice — the same reasoning as the slicing question.
Where this runs
Real CPython, compiled to WebAssembly and running on your own machine — nothing is uploaded. The first run takes a few seconds while the interpreter downloads; after that it is immediate. Need more room, or want to paste your own attempt? Use the Python compiler.


    



Check yourself
0 of 3
Answer without scrolling back up.
  1. Why does one pass suffice?
  2. The longest possible answer is bounded by:
  3. Sorting the list and comparing only the first and last works because:





 Cheat sheet
Longest common prefix
Take the first word as a candidate prefix and shrink it against each following word. The prefix only ever gets shorter, so one pass settles it — O(n·m) in the worst case, and it exits early the moment the prefix is empty.
INTERVIEW · vizlearn.in/interview/longest-common-prefix.html
More in Interview
InterviewImplement substring search (strStr)InterviewIsomorphic stringsInterviewWhat is a Python list underneath?InterviewWhy does [[0]*3]*3 break?
About the author
Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.
About VizLearnGitHubLinkedInContact