Longest Common Prefix in DSA Python

Mental Model

Find the longest starting part that all words share. We compare letters from the start until a difference appears.

Analogy: Imagine several friends starting to sing the same song. The longest common prefix is the part of the song they all sing together before someone changes the words.

words: [flower, flow, flight]
indexes:  0 1 2 3 4
prefix:  ↑ ↑
          f l

Dry Run Walkthrough

Input: words = ["flower", "flow", "flight"]

Goal: Find the longest prefix string common to all words

Step 1: Start with prefix as the first word 'flower'

prefix = 'flower'
words = ['flower', 'flow', 'flight']

Why: We use the first word as the starting point to compare with others

Step 2: Compare prefix 'flower' with second word 'flow' and shorten prefix to match

prefix = 'flow'
words = ['flower', 'flow', 'flight']

Why: We cut prefix to 'flow' because 'flower' and 'flow' share only 'flow' at start

Step 3: Compare prefix 'flow' with third word 'flight' and shorten prefix to match

prefix = 'fl'
words = ['flower', 'flow', 'flight']

Why: We cut prefix to 'fl' because 'flow' and 'flight' share only 'fl' at start

Step 4: No more words to compare, return prefix 'fl'

prefix = 'fl'

Why: This is the longest common prefix among all words

Result:

prefix = 'fl'

Annotated Code

DSA Python

from typing import List

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if not strs:
            return ""
        prefix = strs[0]  # start with first word as prefix
        for word in strs[1:]:
            while not word.startswith(prefix):
                prefix = prefix[:-1]  # shorten prefix by one from the end
                if prefix == "":
                    return ""  # no common prefix
        return prefix

# Driver code
words = ["flower", "flow", "flight"]
sol = Solution()
print(sol.longestCommonPrefix(words))

prefix = strs[0] # start with first word as prefix

initialize prefix to first word to compare with others

for word in strs[1:]:

iterate over remaining words to compare prefix

while not word.startswith(prefix):

reduce prefix until it matches the start of current word

prefix = prefix[:-1] # shorten prefix by one from the end

remove last character from prefix to find common part

if prefix == "": return "" # no common prefix

stop early if no common prefix remains

return prefix

return the longest common prefix found

Output

fl

Complexity Analysis

Time: O(S) because we compare characters of all strings where S is the sum of all characters

Space: O(1) because we only use a few extra variables regardless of input size

vs Alternative: Compared to checking all pairs or characters individually, this approach efficiently reduces prefix length early, saving time

Edge Cases

empty list

returns empty string immediately

DSA Python

if not strs:
    return ""

list with one word

returns the single word as prefix

DSA Python

prefix = strs[0]

no common prefix

returns empty string after shortening prefix to empty

DSA Python

if prefix == "":
    return ""

When to Use This Pattern

When you need to find the common starting part of multiple strings, use the longest common prefix pattern to efficiently find the shared beginning.

Common Mistakes

Mistake: Not shortening the prefix correctly when a word does not start with it
Fix: Use a loop to keep removing the last character from prefix until it matches the start of the current word

Mistake: Not handling empty input list
Fix: Add a check at the start to return empty string if input list is empty

Summary

Finds the longest starting substring common to all strings in a list.

Use when you want to find shared beginnings among multiple words or strings.

Start with the first word as prefix and shorten it step-by-step to fit all words.