Longest Common Prefix

Write a function to find the longest string that is a prefix of every string in the list strs. If there is no common prefix, return the empty string "".

Examples

Input:  strs = ["flower","flow","flight"]   -> "fl"
Input:  strs = ["dog","racecar","car"]      -> ""      # no common prefix
Input:  strs = ["interspecies","interstellar","interstate"] -> "inters"

Constraints

• 1 <= len(strs) <= 200
• 0 <= len(strs[i]) <= 200
• strs[i] consists of lowercase English letters.

Approach — vertical scanning

The common prefix can be no longer than the shortest string, and it's bounded by the very first mismatch in any column. So scan column by column: compare character position 0 across all strings, then position 1, and so on. The first position where a string ends or a character differs is where the prefix stops.

Anchor on the first string strs[0]: for each of its characters, check that every other string has the same character at that index.

Solution

def longest_common_prefix(strs: list[str]) -> str:
    if not strs:
        return ""
    first = strs[0]
    for i, ch in enumerate(first):
        for other in strs[1:]:
            if i >= len(other) or other[i] != ch:
                return first[:i]
    return first

Explanation

• Why anchor on strs[0]? The prefix is shared by all strings, so it must be a prefix of the first one. We walk its characters and confirm each is shared.
• The two stopping conditions: i >= len(other) catches a string that is shorter than the prefix so far (e.g. "flow" inside ["flower","flow"]), and other[i] != ch catches a genuine character mismatch. Either one means the answer is first[:i].
• Falling through the loop means every character of first matched everywhere, so first itself is the common prefix — return it whole.
• Slicing first[:i] is safe even when i == 0, yielding "" for the no-prefix case.

Complexity

• Time: O(S) where S is the total number of characters across all strings — in the worst case (all equal) we touch each character once.
• Space: O(1) extra — we only build the result slice at the end.

Interview tips

Two clean variants exist: vertical (shown here, best early exit) and horizontal (fold the prefix across strings one at a time). A slick Python trick is os.path.commonprefix, or sorting the list and comparing only the first and last elements — mention these to show breadth, but code the explicit scan so your reasoning is visible.