14. Longest Common Prefix

Reformulated question¶

Given a non-empty list of strings, return the longest prefix shared by every string.

Example:

["flower", "flow", "flight"] -> "fl"

Key trick¶

Compare characters column by column across all strings, and stop at the first mismatch.

A clean Python way is zip(*strs).
Each tuple from zip(*strs) contains the characters at the same index in every string.
If all characters in a column are the same, keep it.
Otherwise, stop.

Trap¶

Common mistakes:

Forgetting that an empty string makes the answer "".
Scanning past the shortest string.
Building the answer with repeated string concatenation in a loop.
Overcomplicating with tries or sorting when a direct scan is enough.

Why this question is interesting¶

It tests simple but important interview skills:

turning a string problem into positional comparison
stopping early
writing compact Python with good edge-case handling

Solution with idiomatic Python¶

class Solution:
    def longestCommonPrefix(self, strs: list[str]) -> str:
        # Compare characters at the same position in all strings.
        # zip(*strs) stops at the shortest string automatically.
        prefix = []

        for chars in zip(*strs):
            if len(set(chars)) == 1:
                prefix.append(chars[0])
            else:
                break

        return "".join(prefix)

Pytest test¶

import pytest

@pytest.mark.parametrize(
    ("strs", "expected"),
    [
        (["flower", "flow", "flight"], "fl"),
        (["dog", "racecar", "car"], ""),
        (["interspecies", "interstellar", "interstate"], "inters"),
        (["throne", "throne"], "throne"),
        ([""], ""),
        (["", "abc"], ""),
        (["a"], "a"),
        (["ab", "a"], "a"),
        (["prefix", "prefixes", "prefixing"], "prefix"),
        (["x", "y", "z"], ""),
    ],
)
def test_longest_common_prefix(strs, expected):
    assert Solution().longestCommonPrefix(strs) == expected

Comment on your solution¶

Your solution is correct and easy to follow.

Small improvements:

min([len(s) for s in strs]) can be min(len(s) for s in strs) to avoid an extra list.
prefix += c in a loop is less efficient than appending to a list and "".join(...).
The zip(*strs) version is shorter and naturally handles the shortest string.

import pytest

class Solution:
    def longestCommonPrefix(self, strs: list[str]) -> str:
        min_length = min([len(s) for s in strs])
        prefix = ""
        i = 0
        while (i < min_length):
            c = strs[0][i]
            keep_going = True
            for s in strs:
                if s[i] != c:
                    keep_going = False
                    break
            if keep_going:
                prefix += c
                i += 1
            else:
                break
        return prefix

@pytest.mark.parametrize(
    ("strs", "prefix"),
    [
        (["flower","flow","flight"], "fl"),
        (["dog","racecar","car"], "")
    ]
)
def test_longestCommonPrefix(strs, prefix):
    assert Solution().longestCommonPrefix(strs) == prefix

A cleaned-up version of your style would be:

class Solution:
    def longestCommonPrefix(self, strs: list[str]) -> str:
        min_length = min(len(s) for s in strs)
        prefix = []

        for i in range(min_length):
            c = strs[0][i]
            for s in strs[1:]:
                if s[i] != c:
                    return "".join(prefix)
            prefix.append(c)

        return "".join(prefix)