Longest Common Prefix in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Longest Common Prefix Function

What is the output of the following code that finds the longest common prefix among a list of strings?

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

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

A "flow"

B "f"

C "fl"

D ""

💡 Hint

Check the common starting letters of all strings.

The longest common prefix among "flower", "flow", and "flight" is "fl" because all start with these two letters.

❓ Predict Output

intermediate

Longest Common Prefix with Empty String Present

What will be the output of this code when one string is empty?

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

print(longest_common_prefix(["", "b", "c"]))

A "b"

B ""

C "c"

D None

💡 Hint

If any string is empty, what can the prefix be?

An empty string means no common prefix can exist other than empty string itself.

🔧 Debug

advanced

Identify the Error in Longest Common Prefix Code

What error will this code produce when run?

DSA Python

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

print(longest_common_prefix([]))

A IndexError

B Returns empty string ""

C TypeError

D Infinite loop

💡 Hint

What happens if strs is an empty list?

The code does not check if strs is empty before accessing strs[0], causing an IndexError.

🧠 Conceptual

advanced

Longest Common Prefix Algorithm Complexity

What is the time complexity of the standard longest common prefix algorithm that compares characters one by one among n strings of average length m?

A O(n * m)

B O(n + m)

C O(m^2)

D O(n^2)

💡 Hint

Consider how many characters are compared in total.

The algorithm compares each character of each string up to the prefix length, resulting in O(n * m) time.

🚀 Application

expert

Longest Common Prefix in Trie Data Structure

Given a trie built from the strings ["interview", "interrupt", "integrate", "integral"], what is the longest common prefix represented by the trie?

A "integr"

B "int"

C "inter"

D "inte"

💡 Hint

Find the deepest node in the trie where all strings share the same path.

All strings share "inte" as prefix. After that, paths diverge.