Longest Common Prefix¶

Problem¶

Given a list of strings, return the longest common prefix shared by all of them.

Approach¶

Vertical scanning: compare character-by-character across all strings. Use the first string as reference; stop when any string differs or is exhausted.

When to Use¶

Autocomplete, trie-based search, file path commonality. Simple but frequently asked.

Complexity¶


Time	`O(S) where S = sum of all string lengths`
Space	`O(1) — only stores the prefix end index`

Implementation¶

SolutionTestsChallenge

longest_common_prefix ¶

Longest Common Prefix — find the longest common prefix among strings.

Problem

Given a list of strings, return the longest common prefix shared by all of them.

Approach

Vertical scanning: compare character-by-character across all strings. Use the first string as reference; stop when any string differs or is exhausted.

When to use

Autocomplete, trie-based search, file path commonality. Simple but frequently asked.

Complexity

Time: O(S) where S = sum of all string lengths Space: O(1) — only stores the prefix end index

longest_common_prefix ¶

longest_common_prefix(strs: Sequence[str]) -> str

Return the longest common prefix of all strings in strs.

longest_common_prefix(["flower", "flow", "flight"]) 'fl' longest_common_prefix(["dog", "racecar", "car"]) ''

Source code in src/algo/strings/longest_common_prefix.py

def longest_common_prefix(strs: Sequence[str]) -> str:
    """Return the longest common prefix of all strings in *strs*.

    >>> longest_common_prefix(["flower", "flow", "flight"])
    'fl'
    >>> longest_common_prefix(["dog", "racecar", "car"])
    ''
    """
    if not strs:
        return ""

    for i, ch in enumerate(strs[0]):
        for s in strs[1:]:
            if i >= len(s) or s[i] != ch:
                return strs[0][:i]

    return strs[0]

tests/strings/test_longest_common_prefix.py

"""Tests for the longest common prefix problem."""

from hypothesis import given
from hypothesis import strategies as st

from algo.strings.longest_common_prefix import longest_common_prefix


class TestLongestCommonPrefix:
    def test_basic(self) -> None:
        assert longest_common_prefix(["flower", "flow", "flight"]) == "fl"

    def test_no_common_prefix(self) -> None:
        assert longest_common_prefix(["dog", "racecar", "car"]) == ""

    def test_empty_list(self) -> None:
        assert longest_common_prefix([]) == ""

    def test_single_string(self) -> None:
        assert longest_common_prefix(["alone"]) == "alone"

    def test_identical_strings(self) -> None:
        assert longest_common_prefix(["abc", "abc", "abc"]) == "abc"

    def test_empty_string_in_list(self) -> None:
        assert longest_common_prefix(["", "abc", "abd"]) == ""

    @given(
        prefix=st.text(alphabet="abc", min_size=1, max_size=10),
        suffixes=st.lists(
            st.text(alphabet="xyz", min_size=0, max_size=10),
            min_size=1,
            max_size=5,
        ),
    )
    def test_constructed_prefix_is_found(
        self, prefix: str, suffixes: list[str]
    ) -> None:
        strs = [prefix + s for s in suffixes]
        result = longest_common_prefix(strs)
        assert result.startswith(prefix) or prefix.startswith(result)
        # result must be at least as long as prefix
        assert len(result) >= len(prefix)

Implement it yourself

Run: just challenge strings longest_common_prefix

Then implement the functions to make all tests pass. Use just study strings for watch mode.

Reveal Solution

longest_common_prefix ¶

Longest Common Prefix — find the longest common prefix among strings.

Problem

Given a list of strings, return the longest common prefix shared by all of them.

Approach

Vertical scanning: compare character-by-character across all strings. Use the first string as reference; stop when any string differs or is exhausted.

When to use

Autocomplete, trie-based search, file path commonality. Simple but frequently asked.

Complexity

Time: O(S) where S = sum of all string lengths Space: O(1) — only stores the prefix end index

longest_common_prefix ¶

longest_common_prefix(strs: Sequence[str]) -> str

Return the longest common prefix of all strings in strs.

longest_common_prefix(["flower", "flow", "flight"]) 'fl' longest_common_prefix(["dog", "racecar", "car"]) ''

Source code in src/algo/strings/longest_common_prefix.py

def longest_common_prefix(strs: Sequence[str]) -> str:
    """Return the longest common prefix of all strings in *strs*.

    >>> longest_common_prefix(["flower", "flow", "flight"])
    'fl'
    >>> longest_common_prefix(["dog", "racecar", "car"])
    ''
    """
    if not strs:
        return ""

    for i, ch in enumerate(strs[0]):
        for s in strs[1:]:
            if i >= len(s) or s[i] != ch:
                return strs[0][:i]

    return strs[0]