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.

Practice

1. What does the Longest Common Prefix (LCP) problem ask you to find given a list of strings?

easy

A. The total number of strings in the list

B. The longest starting substring common to all strings

C. The longest substring common to any two strings

D. The longest ending substring common to all strings

Solution

1. Step 1: Understand the problem definition

   The Longest Common Prefix means the longest substring at the start of all strings that is the same.

2. Step 2: Compare options with the definition

   Only The longest starting substring common to all strings matches this definition exactly.

3. Final Answer:

   The longest starting substring common to all strings -> Option B

4. Quick Check:

   Longest Common Prefix = longest starting substring [OK]

Hint: Focus on the start of strings, not anywhere else [OK]

Common Mistakes:

• Confusing prefix with suffix
• Thinking about any substring instead of prefix
• Counting total strings instead of prefix length

2. Which of the following Python code snippets correctly initializes a variable to store the longest common prefix as an empty string?

easy

A. lcp = None

B. lcp = []

C. lcp = ''

D. lcp = 0

Solution

1. Step 1: Identify the correct data type for prefix storage

   The longest common prefix is a string, so it should be initialized as an empty string.

2. Step 2: Match initialization with data type

   lcp = '' initializes lcp as an empty string, which is correct.

3. Final Answer:

   lcp = '' -> Option C

4. Quick Check:

   Prefix is a string, so empty string initialization [OK]

Hint: Use empty string '' to start prefix, not list or number [OK]

Common Mistakes:

• Using list [] instead of string
• Using None which is not a string
• Using 0 which is a number, not string

3. What will be the output of the following Python code?

def longest_common_prefix(strs):
    if not strs:
        return ''
    prefix = strs[0]
    for s in strs[1:]:
        while not s.startswith(prefix):
            prefix = prefix[:-1]
            if not prefix:
                return ''
    return prefix

print(longest_common_prefix(['flower', 'flow', 'flight']))

medium

A. fl

B. flow

C. f

D. flower

Solution

1. Step 1: Initialize prefix and iterate over strings

   Prefix starts as 'flower'. Check 'flow': 'flow' does not start with 'flower', so remove last char to 'flowe', then 'flow', which matches.

2. Step 2: Check next string 'flight'

   'flight' does not start with 'flow', remove last char to 'flo', no match; then 'fl', which matches.

3. Final Answer:

   fl -> Option A

4. Quick Check:

   Common start of all strings = 'fl' [OK]

Hint: Shrink prefix until all strings start with it [OK]

Common Mistakes:

• Returning first string without checking others
• Not shrinking prefix correctly
• Confusing substring anywhere with prefix

4. The following code is intended to find the longest common prefix but has a bug. What is the bug?

def longest_common_prefix(strs):
    prefix = strs[0]
    for s in strs:
        while not s.startswith(prefix):
            prefix = prefix[:-1]
    return prefix

print(longest_common_prefix(['dog', 'racecar', 'car']))

medium

A. No return statement inside the loop

B. Loop starts from first string causing incorrect prefix update

C. Using s.startswith(prefix) instead of prefix.startswith(s)

D. Missing check for empty prefix causing infinite loop

Solution

1. Step 1: Analyze loop and prefix shrinking

   The code shrinks prefix until s starts with prefix, but does not check if prefix becomes empty.

2. Step 2: Identify infinite loop risk

   If no common prefix exists, prefix will shrink to empty string, then prefix[:-1] stays empty, causing infinite loop.

3. Final Answer:

   Missing check for empty prefix causing infinite loop -> Option D

4. Quick Check:

   Empty prefix check needed to stop loop [OK]

Hint: Always check if prefix is empty to avoid infinite loops [OK]

Common Mistakes:

• Not checking prefix empty condition
• Looping over all strings including first
• Confusing startswith arguments

5. Given a list of strings, how would you efficiently find the longest common prefix using a vertical scanning approach? Which of the following best describes the method?

hard

A. Compare characters column by column across all strings until a mismatch is found

B. Sort the strings and compare only the first and last strings completely

C. Use a hash map to count character frequencies at each position

D. Concatenate all strings and find the longest substring

Solution

1. Step 1: Understand vertical scanning

   Vertical scanning means checking each character position across all strings one by one.

2. Step 2: Identify stopping condition

   Stop when a mismatch or end of any string is found at that position.

3. Final Answer:

   Compare characters column by column across all strings until a mismatch is found -> Option A

4. Quick Check:

   Vertical scanning = column-wise character comparison [OK]

Hint: Check characters by columns, stop at first mismatch [OK]

Common Mistakes:

• Confusing vertical scanning with sorting
• Using hash maps unnecessarily
• Concatenating strings instead of comparing