Longest Common Prefix

Description

14. Longest Common Prefix

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: strs = ["flower","flow","flight"]
Output: "fl"

Example 2:
Input: strs = ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.

Constraints:

• $1\le \text{strs.length}\le 200$
• $0\le \text{strs[i].length}\le 200$
• strs[i] consists of only lowercase English letters if it is non-empty.

---

Approach 1: Horizontal Scanning ($O(S)$ Time, $O(1)$ Space)

Intuition

Start by assuming the first string strs[0] is the common prefix. Iterate through the remaining strings and continuously trim characters off the end of the prefix until it is a valid prefix of the current string (strs[i].indexOf(prefix) == 0). If the prefix becomes empty at any point, return "".

class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) return "";
 
        String prefix = strs[0];
 
        for (int i = 1; i < strs.length; i++) {
            // Trim prefix until it matches the start of strs[i]
            while (strs[i].indexOf(prefix) != 0) {
                prefix = prefix.substring(0, prefix.length() - 1);
                if (prefix.isEmpty()) return "";
            }
        }
 
        return prefix;
    }
}
 

Complexity

• Time Complexity: $O(S)$ — Where $S$ is the total number of characters across all strings in the array.
• Space Complexity: $O(1)$ auxiliary space.

---

Approach 2: Sorting Comparison ($O(N\log N\cdot M)$ Time, $O(1)$ Space)

Intuition

Sort the array lexicographically (alphabetically). After sorting, the strings that are most different will be at the first and last indices of the array. The longest common prefix for the entire array will simply be the common prefix between strs[0] and strs[strs.length - 1].

import java.util.Arrays;
 
class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) return "";
 
        // Sort the array lexicographically
        Arrays.sort(strs);
 
        String first = strs[0];
        String last = strs[strs.length - 1];
        int i = 0;
 
        // Compare characters between the first and last strings
        while (i < first.length() && i < last.length() && first.charAt(i) == last.charAt(i)) {
            i++;
        }
 
        return first.substring(0, i);
    }
}
 

Complexity

• Time Complexity: $O(N\log N\cdot M)$ — Where $N$ is the number of strings and $M$ is the maximum length of a string (due to sorting).
• Space Complexity: $O(1)$ auxiliary space (ignoring internal sorting stack space).

---

Easy Memory Rule

“Either assume strs[0] is the prefix and trim it down, OR sort the array and compare only the first and last strings!”