Problem Narrative

You’re building an autocomplete service for a high-traffic e-commerce marketplace (millions of daily active users). When a shopper types into the search bar, your service receives a list of candidate query completions (already filtered by locale and popularity). To keep latency low and UI behavior consistent, you want to compute the longest common prefix shared by all candidates—this prefix can be highlighted as the “stable” part of the suggestion list.

A single request may include up to tens of thousands of candidate strings (e.g., brand names, product categories, and trending queries). Your implementation should be efficient and handle edge cases cleanly.

Task

Implement a function:

• Input: strs: list[str] — an array of strings.
• Output: str — the longest common prefix among all strings in strs. If there is no common prefix, return an empty string "".

A prefix is a substring that starts at index 0 of a string.

Examples

Example 1

Input: strs = ["interstellar", "internet", "internal", "into"]

Output: "int"

Explanation: All strings start with "int". The next character differs ('e', 'e', 'e', 'o'), so the longest common prefix is "int".

Example 2

Input: strs = ["pay", "payout", "paypal", "panel"]

Output: "pa"

Explanation: All strings share "pa". At index 2, the characters diverge ('y' vs 'n'), so the answer is "pa".

Notes / Clarifications

1. If strs is empty, return "".
2. If any string is empty, the longest common prefix is "".
3. Strings may contain lowercase/uppercase English letters, digits, spaces, or punctuation—treat them as ordinary characters (case-sensitive).

Constraints

• 0 <= strs.length <= 2 * 10^4
• 0 <= strs[i].length <= 200
• Total characters across all strings <= 2 * 10^5