Longest Common Prefix

Problem

Given an array of strings, find the longest common prefix shared among all strings in the array. A common prefix is a string that appears at the beginning of every string in the array.

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

Input / Output Format

Input: An array of strings strs where each element is a non-empty lowercase English string.

Output: A single string representing the longest common prefix among all strings. Return "" if none exists.

Examples

Example 1

Input: strs = ["flower", "flow", "flight"] Output: "fl" Explanation: All three strings start with "fl". The third character differs (o vs i), so the prefix stops at "fl".

Example 2

Input: strs = ["dog", "racecar", "car"] Output: "" Explanation: There is no common starting character among the three strings, so the answer is an empty string.

Example 3

Input: strs = ["interview", "inter", "internal", "interstate"] Output: "inter" Explanation: All strings begin with "inter". The 6th character differs across words, so the prefix ends at "inter".

Approach Hints

Approach 1 — Horizontal Scanning: Start by assuming the first string is the full prefix. Iterate through each subsequent string, and progressively trim the prefix until it matches the start of the current string. If the prefix ever becomes empty, return "".

Approach 2 — Vertical Scanning: Compare character by character across all strings at the same index position. Stop as soon as any string either runs out of characters or has a mismatch at that index.

Approach 3 — Divide and Conquer (Advanced): Split the array in half, recursively find the longest common prefix for each half, then find the common prefix of those two results.

Key Insight: The longest common prefix can be at most as long as the shortest string in the array. This is a useful optimization — find the minimum-length string first, then only scan up to that length.

Time Complexity: O(S) where S is the sum of all characters across all strings in the worst case. Space Complexity: O(1) extra space (not counting the output).