Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string "".

Example 1:

Input:
3
flower flow flight
Output: fl

Example 2:

Input:
3
dog racecar car
Output:

Constraints:

• 1 ≤ strs.length ≤ 200
• 0 ≤ strs[i].length ≤ 200
• strs[i] consists of only lowercase English letters

Input format: First line: number of strings n. Second line: n space-separated strings.

Output format: The longest common prefix, or empty line if none.