14. Longest Common Prefix
You are given a list of strings strs. Return the longest string that every string in the list starts with — the longest common prefix of the whole list.
If the strings share no leading characters at all (or any of them is empty), the longest common prefix is the empty string: return "", which prints as an empty line.
Example 1:
Input: strs = ["flower", "flow", "flight"]
Output: "fl"
Explanation: All three strings start with "fl". They disagree at the third character (o vs o vs i — "flight" breaks it), so "fl" is the longest shared start.
Example 2:
Input: strs = ["dog", "racecar", "car"]
Output: ""
Explanation: The very first characters already differ (d, r, c), so nothing is shared and the answer is the empty string.
Constraints:
- 1 ≤ strs.length ≤ 200
- 0 ≤ strs[i].length ≤ 200
- strs[i] consists of lowercase English letters only
Hints:
The answer can never be longer than the shortest string in the list. That gives you a hard cap on how far to look.
Vertical scan: compare column by column — check that character 0 matches everywhere, then character 1, and stop at the first column with a mismatch (or when some string runs out).
Horizontal scan: keep a running prefix, starting as strs[0], and shrink it from the back until the next string starts with it. Repeat for every string.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: strs = ["flower", "flow", "flight"]
Expected output: "fl"