Longest Common Prefix

Table of Contents +

This one looks simple. You get a list of words. You find the starting part they all share. But the interviewer is watching something else. They want to see if you stop scanning at the right moment. They want to see if you handle the empty list. They also want to see the case where nothing matches. So the real test here is careful comparison, not fancy tricks.

🧩 The Problem

You are given an array of strings. Your job is to find the longest prefix that every string shares. A prefix means the part at the start of a word. So for “flower” the prefixes are “f”, “fl”, “flo”, and so on. If the strings share nothing at the start, you return an empty string.

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

Input:  ["dog", "cat", "fish"]
Output: ""

See in the first example, all three words start with “fl”. The third word “flight” breaks at the next letter. So we stop there and return “fl”.

🐢 The Simple Approach First

The first idea most people get is this. Take the first word as a guess for the answer. Then check it against every other word. If a word does not start with your guess, you cut the guess shorter. You keep cutting until every word agrees.

This works fine. But it feels a bit clumsy. You keep using a shrinking guess and re-checking from the start each time. In an interview you can mention this idea. Then say you have a cleaner one.

🏇 The Better Approach: Vertical Scanning

Here is the cleaner way. Instead of comparing whole words, you compare one column at a time. Think of the words stacked on top of each other like a table. You look at the first letter of every word. Are they all the same? Good, move to the second letter. Keep going down the columns.

The moment one column has a mismatch, you stop. Everything before that column is your answer. You also stop if you reach the end of the shortest word. This is called vertical scanning because you read the words top to bottom, column by column.

f l o w e r
f l o w
f l i g h t
^ ^ ^
| | └── mismatch at index 2 (o vs o vs i)
| └──── all match
└────── all match

Answer = "fl"

Why is this nicer? You never build and shrink a guess. You walk forward only. The first mismatch ends everything right away.

📝 Steps to Solve It

If the array is empty, return an empty string straight away.
Take the first word. Walk through its characters one by one. Call the position i.
For each position i, look at that same character in every other word.
If any word is shorter than i, or its character does not match, stop.
Return the part of the first word from the start up to position i.

💻 The Code

We compare each character of the first word against the same spot in all the other words. The first mismatch ends the loop.

[data-tabs] [role="tablist"], [data-tabs] [data-scroll] { display: none !important; } [data-tabs] [role="tabpanel"] { display: block !important; } [data-tabs] [role="tabpanel"] + [role="tabpanel"] { margin-top: 1rem; }

def longest_common_prefix(words):
    if not words:               # empty list, nothing to share
        return ""
    # Walk through each character of the first word
    for i, c in enumerate(words[0]):
        for w in words[1:]:
            # Word ended here or characters differ, so stop
            if i >= len(w) or w[i] != c:
                return words[0][:i]
    return words[0]             # first word is itself the prefix


words = ["flower", "flow", "flight"]
print(f'Prefix: "{longest_common_prefix(words)}"')

The output of the above code will be:

Prefix: "fl"

Note

In the C version there is no explicit length check inside the inner loop. It still works because the strings live in fixed char[20] buffers and end with a '\0'. When a word ends early, its '\0' will not match the first word’s letter, so the scan stops at the right spot. The C++, Java, Python, and JavaScript versions use an explicit i >= length check instead. Both styles do the same job.

⏱️ Time and Space Complexity

Here n is the number of words and m is the length of the shortest word. In the worst case we compare every character of every word once.

Approach	Time	Space
Shrinking guess	O(n * m)	O(1)
Vertical scanning	O(n * m)	O(1)

Both approaches have the same big-O time. But vertical scanning often finishes early. If the very first column has a mismatch, you stop right away without touching the rest of the words. The space is O(1) extra because you only hold the prefix you return.

Tip

The fastest stop happens when the first letters differ. So if any two words start with a different letter, your answer is an empty string and you are done in one step. Mention this early-exit point in the interview. It shows you think about the best case, not just the worst.

Caution

Watch the empty cases. An empty array should return an empty string. And remember a word can be shorter than the others. If you only check words[w][i] != c without checking the length first, you can read past the end of a short word and crash. Always check the length before you read the character. In C the '\0' at the end of each string acts as that length check for you.

🎯 Key Takeaways

✅ Vertical scanning compares one column of characters across all words, then moves to the next column.
✅ You stop at the first mismatch, or when you reach the end of the shortest word.
✅ The time is O(n * m) where n is the number of words and m is the shortest word length.
✅ The extra space is O(1) because you only return the shared prefix.
✅ Always handle the empty array and the shorter-word case so your code does not crash.

Check Your Knowledge

Test what you learned. Pick an answer for each question, then click Check.

🚀 What’s Next?

Check Anagram
String Operations

Previous Check if Two Strings are Anagrams Next String Compression

Share & Connect

Share on LinkedIn