Find Longest Common Prefix in Java
Problem
A common prefix is a run of characters that every string in a group begins with; the longest common prefix is the longest such run, which may be empty.
Given an array of words, find the longest prefix they all share.
Java Program
public class LongestCommonPrefix {
public static void main(String[] args) {
String[] words = {"interview", "internet", "interval", "internal"};
String first = words[0];
int length = 0;
outer:
for (int i = 0; i < first.length(); i++) {
char c = first.charAt(i);
for (String w : words) {
if (i >= w.length() || w.charAt(i) != c) { // a word ended or disagreed at column i
break outer;
}
}
length++; // every word shares this column
}
String prefix = first.substring(0, length);
System.out.println("Longest common prefix: \"" + prefix + "\"");
}
}Output
Core Logic
Comparing the words column by column — first characters, then second characters, and so on — stops at the first column where any word disagrees or runs out.
- 1The first word supplies the candidate character for each column
i. - 2The inner loop checks every word at column
i; a word that is too short or holds a different character ends the search. - 3
break outerexits both loops at once, so no further columns are checked. - 4
lengthcounts the columns every word agreed on, andsubstring(0, length)extracts the prefix.
i-n-t-e-r in all four words; at column 5 the words have v, n, v, n, so the search stops.Key Point: The i >= w.length() check must come before w.charAt(i) — otherwise a shorter word would throw StringIndexOutOfBoundsException.
Why: In the worst case each of the n words is checked at each of the m prefix positions; apart from the result, only counters are stored.
Key Concepts
Approach 2: Sort and Compare Ends
import java.util.Arrays;
public class LongestCommonPrefixSorted {
public static void main(String[] args) {
String[] words = {"interview", "internet", "interval", "internal"};
String[] sorted = words.clone();
Arrays.sort(sorted); // alphabetical order puts the most different words at the two ends
String low = sorted[0];
String high = sorted[sorted.length - 1];
int i = 0;
while (i < low.length() && i < high.length() && low.charAt(i) == high.charAt(i)) {
i++;
}
System.out.println("Longest common prefix: \"" + low.substring(0, i) + "\"");
}
}
Output
Core Logic
After sorting alphabetically, the first and last words are the most different pair, so whatever prefix they share is shared by every word in between.
- 1
words.clone()is sorted, leaving the original array untouched. - 2
sorted[0]andsorted[sorted.length - 1]are the alphabetically first and last words. - 3A single loop counts how many leading characters those two words have in common.
internal, internet, interval, interview; internal and interview share inter.Key Point: Only two comparisons are needed after sorting, but the sort itself costs more — this approach trades raw speed for very short code.
Why: Sorting n strings takes O(n log n) comparisons, each up to m characters long, and the cloned array uses O(n) references.
Key Concepts
Interview Questions
What is the result when the words share nothing?
The empty string. It's a valid answer, so return "" rather than null.
What's the complexity of the vertical scan?
O(S), where S is the total number of characters across all words, in the worst case when every word is identical.