How do you find the longest common prefix of an array of strings?

Start with the first string as the candidate prefix, then shorten it until every other string starts with it. Alternatively, compare characters column by column across all strings and stop at the first mismatch. Both approaches are O(total characters).

Key Points: • If the array is empty, the prefix is "". • Horizontal approach: prefix = strs[0]; for each other string, while it doesn't start with prefix, remove the last character. • Vertical approach: for index i, check the i-th character of every string; stop when a string ends or a character differs. • A neat trick: sort the array, then compare only the first and last strings, because they differ the most. • It's a common LeetCode warm-up question (problem 14).

Code Example:

import java.util.Arrays;

public class LongestCommonPrefix {

    // Vertical scanning
    static String lcp(String[] strs) {
        if (strs == null || strs.length == 0) return "";
        for (int i = 0; i < strs[0].length(); i++) {
            char c = strs[0].charAt(i);
            for (int j = 1; j < strs.length; j++) {
                if (i == strs[j].length() || strs[j].charAt(i) != c) {
                    return strs[0].substring(0, i);
                }
            }
        }
        return strs[0];
    }

    // Sorting trick: only the first and last strings need comparing
    static String lcpSorted(String[] strs) {
        String[] copy = strs.clone();
        Arrays.sort(copy);
        String first = copy[0], last = copy[copy.length - 1];
        int i = 0;
        while (i < first.length() && i < last.length() && first.charAt(i) == last.charAt(i)) i++;
        return first.substring(0, i);
    }

    public static void main(String[] args) {
        String[] a = {"interview", "internet", "interval", "internal"};
        String[] b = {"spring", "java", "kafka"};
        System.out.println("\"" + lcp(a) + "\"");
        System.out.println("\"" + lcpSorted(a) + "\"");
        System.out.println("\"" + lcp(b) + "\"");
    }
}

Output:

"inter" "inter" ""

Good to Know: The sorting trick is O(n log n × m) because of the sort, so it's elegant rather than faster. In an interview, present vertical scanning as the main solution and mention the sorting idea as an alternative.

Interview Tip: A concise interview answer is:

"I compare characters column by column: for each index I check that every string has the same character there, and I stop at the first string that ends or differs, returning the prefix up to that index. It's O(total characters) with no extra space; another neat option is to sort the array and compare only the first and last strings."

Previous question: How do you check whether one string is a rotation of another?

How do you find the longest common prefix of an array of strings?

More Java Strings interview questions