Longest common prefix of a list of strings

Given a list of strings, return the longest prefix that every string starts with. Return an empty string if they share none.

Interface

Unless you agree on a different interface with the interviewer, assume:

• longest_common_prefix(strs: list[str]) -> str — an empty list returns "".

Example

longest_common_prefix(["flower", "flow", "flight"])            ->  "fl"
longest_common_prefix(["dog", "racecar", "car"])               ->  ""
longest_common_prefix(["interview", "internet", "interval"])   ->  "inter"
longest_common_prefix(["solo"])                                ->  "solo"

Constraints

• 0 <= len(strs) <= 200, each string 0 to 200 characters.

Clarifying questions

• What should an empty list return?
• Can strings be empty?
• Is it ASCII or Unicode, and does case matter?
• Will the same list be queried repeatedly, or new strings added?

What a strong answer covers

• Vertical scan: compare character i of every string until one differs or a string ends. O(S) time where S is the total number of characters, O(1) extra space.
• Alternatives: start from the first string and shrink it; sort and compare only the first and last; divide and conquer; a trie.
• Edge cases: empty list, an empty string in the list, a single string, one string a prefix of another.
• Complexity of each approach and why the vertical scan stops early.

Follow-ups

• Strings arrive one at a time; keep the current common prefix.
• Answer "longest common prefix of strings i to j" for many queries.
• Find the longest common prefix shared by at least k of the strings.