Python Program to Find Longest Common Prefix

Use a function that compares characters of strings one by one using zip() and set() to find the longest common prefix, like def longest_common_prefix(strs): prefix = ''; for chars in zip(*strs): if len(set(chars)) == 1: prefix += chars[0] else: break; return prefix.

Examples

Input["flower", "flow", "flight"]

Output"fl"

Input["dog", "racecar", "car"]

Output""

Input["interview", "internet", "internal"]

Output"int"

How to Think About It

To find the longest common prefix, look at the first character of each string and check if they are all the same. If yes, add that character to the prefix. Then move to the next character and repeat until you find a difference or reach the end of any string.

Algorithm

1

Check if the list of strings is empty; if yes, return an empty string.

2

Take characters from each string at the same position using a loop.

3

Compare these characters; if all are the same, add the character to the prefix.

4

Stop when characters differ or any string ends.

5

Return the collected prefix.

Code

python

def longest_common_prefix(strs):
    if not strs:
        return ""
    prefix = ""
    for chars in zip(*strs):
        if len(set(chars)) == 1:
            prefix += chars[0]
        else:
            break
    return prefix

# Example usage
strings = ["flower", "flow", "flight"]
print(longest_common_prefix(strings))

Output

fl

Dry Run

Let's trace the example ['flower', 'flow', 'flight'] through the code

1

Check empty list

Input list is ['flower', 'flow', 'flight'], not empty, continue.

2

Loop over characters by position

zip(*strs) gives tuples: ('f','f','f'), ('l','l','l'), ('o','o','i'), ...

3

Compare characters in each tuple

First tuple ('f','f','f') all same, add 'f' to prefix -> prefix = 'f'. Second tuple ('l','l','l') all same, add 'l' -> prefix = 'fl'. Third tuple ('o','o','i') not all same, stop loop.

4

Return prefix

Return 'fl' as longest common prefix.

Iteration	Characters	All Same?	Prefix
1	('f','f','f')	Yes	f
2	('l','l','l')	Yes	fl
3	('o','o','i')	No	fl

Why This Works

Step 1: Check if input is empty

If the list of strings is empty, return an empty string immediately because there is no prefix.

Step 2: Compare characters at each position

Using zip(*strs) groups characters from all strings at the same index, making it easy to compare them.

Step 3: Build prefix until mismatch

If all characters in a group are the same, add that character to the prefix; stop when a difference is found.

Alternative Approaches

Horizontal scanning

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"]))

This method compares prefixes by shrinking the prefix string until it matches all strings; it can be slower if strings are long.

Divide and conquer

python

def common_prefix(left, right):
    min_len = min(len(left), len(right))
    for i in range(min_len):
        if left[i] != right[i]:
            return left[:i]
    return left[:min_len]

def longest_common_prefix(strs):
    if not strs:
        return ""
    if len(strs) == 1:
        return strs[0]
    mid = len(strs) // 2
    left = longest_common_prefix(strs[:mid])
    right = longest_common_prefix(strs[mid:])
    return common_prefix(left, right)

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

This method splits the list and merges prefixes recursively; it is efficient for large lists.

Complexity: O(S) time, O(1) space

Time Complexity

The time depends on the total number of characters in all strings until the first mismatch. In the worst case, all strings are the same, so it checks all characters, O(S), where S is the sum of all characters.

Space Complexity

Only a few extra variables are used, so space is O(1), constant space.

Which Approach is Fastest?

The zip and set method is simple and fast for most cases. Horizontal scanning can be slower if prefix shrinks many times. Divide and conquer is good for very large lists.

Approach	Time	Space	Best For
Zip and set	O(S)	O(1)	Simple and short code
Horizontal scanning	O(S)	O(1)	When strings are few and prefix is short
Divide and conquer	O(S)	O(log n)	Large lists with many strings