Longest Common Prefix in DSA Python - Execution Trace

Concept Flow - Longest Common Prefix

Start with first string as prefix

↓

Compare prefix with next string

↓

Reduce prefix length until it matches

↓

Move to next string

↓

All strings checked?

No→Repeat comparison

Yes↓

Return prefix

Start with the first string as the prefix. Compare it with each next string, reducing prefix length until it matches. Repeat for all strings, then return the prefix.

Execution Sample

DSA Python

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

Finds the longest common prefix string among an array of strings by shrinking the prefix until it matches all strings.

Execution Table

Step	Operation	Current String	Prefix Before	Prefix After	Visual State
1	Initialize prefix	N/A	N/A	flower	prefix = 'flower'
2	Compare prefix with 'flow'	flow	flower	flow	prefix reduced to 'flow' because 'flow' does not start with 'flower'
3	Compare prefix with 'flight'	flight	flow	fl	prefix reduced to 'fl' because 'flight' does not start with 'flow' or 'flo'
4	All strings checked	N/A	fl	fl	Final prefix is 'fl'

💡 All strings checked, prefix 'fl' matches all strings

Variable Tracker

Variable	Start	After Step 2	After Step 3	Final
prefix	flower	flow	fl	fl
current string	N/A	flow	flight	N/A

Key Moments - 3 Insights

Why do we reduce the prefix instead of increasing it?

Because we start with the first string as the longest possible prefix. We reduce it only when the next string does not start with it, as shown in steps 2 and 3 of the execution_table.

What happens if the prefix becomes empty?

If the prefix becomes empty, it means there is no common prefix among the strings. The loop stops and returns an empty string. This is implied in the while loop in step 3.

Why do we check 's.startswith(prefix)' inside a while loop?

Because the prefix may need to be shortened multiple times until it matches the start of the current string, as shown in step 3 where prefix shrinks from 'flow' to 'fl'.

Visual Quiz - 3 Questions

Look at the execution_table, what is the prefix after comparing with the second string?

A flower

B flow

C fl

D flight

💡 Hint

Check Step 2 in the execution_table where prefix changes after comparing with 'flow'

At which step does the prefix become 'fl'?

A Step 1

B Step 2

C Step 3

D Step 4

💡 Hint

Look at the prefix after Step 3 in the execution_table

If the input strings were ['dog', 'racecar', 'car'], what would happen to the prefix?

A It would become empty ''

B It would become 'd'

C It would remain 'dog'

D It would become 'car'

💡 Hint

Think about prefix reduction when no common start exists, as explained in key_moments

Concept Snapshot

Longest Common Prefix:
- Start with first string as prefix
- Compare prefix with each string
- While prefix not matching start, reduce prefix
- Return prefix after all strings checked
- Empty prefix means no common prefix

Full Transcript

The longest common prefix algorithm starts by assuming the first string is the prefix. It then compares this prefix with each subsequent string. If the current string does not start with the prefix, the prefix is shortened by removing the last character. This process repeats until the prefix matches the start of the current string or becomes empty. After checking all strings, the remaining prefix is returned as the longest common prefix. If the prefix becomes empty, it means no common prefix exists among the strings.