# Common Prefix

> They all start the same way. How far?

Canonical URL: <https://datadriven.io/problems/common_prefix>

Domain: Python · Difficulty: hard · Seniority: L4

## Problem

Given a list of strings, return the longest string that is a prefix of every string. Return empty string if there is no common prefix or the list is empty.

## Worked solution and explanation

### Why this problem exists in real interviews

Finding the longest common prefix tests **character-by-character comparison across multiple strings** and **early termination**. It is a classic string problem that reveals whether you can handle boundary conditions cleanly.

> **Trick to Solving**
>
> Use the first string as the candidate prefix and shrink it character by character. At each position, check if all strings share the same character. Stop as soon as any string differs or is too short.

---

### Break down the requirements

#### Step 1: Handle edge cases: empty list or empty first string

An empty list has no common prefix. An empty first string means the prefix is empty.

#### Step 2: Iterate by character position

For each index in the first string, check if every other string has the same character at that position.

#### Step 3: Return the prefix when a mismatch is found

Slice the first string from 0 to the mismatch index. If no mismatch occurs, the entire first string is the prefix.

---

### The solution

**Vertical scan across all strings**

```python
def longest_prefix(strs):
    if not strs:
        return ''
    prefix_len = 0
    for i in range(len(strs[0])):
        char = strs[0][i]
        for s in strs[1:]:
            if i >= len(s) or s[i] != char:
                return strs[0][:prefix_len]
        prefix_len += 1
    return strs[0][:prefix_len]
```

> **Time and Space Complexity**
>
> **Time:** O(S) where S is the total number of characters across all strings. In the worst case, every character is compared.
> 
> **Space:** O(1) beyond the return value. No auxiliary data structures.

> **Interviewers Watch For**
>
> Early termination at the first mismatch rather than scanning all characters and then trimming. This shows you reason about efficiency even on string problems.

> **Common Pitfall**
>
> Using `min(strs)` and `max(strs)` as a shortcut. While clever, this only works for lexicographic prefix comparison and obscures the logic in interviews.

---

## Common follow-up questions

- What if the list contains thousands of very long strings? _(Tests whether you would sort first and compare only the first and last strings, which is O(n log n) but reduces comparisons.)_
- How would you adapt this for longest common suffix? _(Tests reversing each string, finding the prefix, then reversing the result.)_
- What if you needed the longest common substring instead of prefix? _(Tests knowledge of dynamic programming or suffix array approaches for a much harder problem.)_

## Related

- [All practice problems](https://datadriven.io/problems)
- [Mock interview mode](https://datadriven.io/interview/common_prefix)
- [Python Interview Questions](https://datadriven.io/python-interview-questions)
- [Data Engineering Interview Prep Guide](https://datadriven.io/data-engineer-interview-prep)
- [Daily Challenge](https://datadriven.io/daily)

---

Source: DataDriven (https://datadriven.io). 100% free data engineering interview prep. Live code execution against Postgres 16, Python 3.11, and Spark sandboxes. No paywall, no premium tier, no signup gate.