Understanding Longest Common Prefix in Java

The Challenge & Real-World Use Cases

Determining the longest common prefix among a set of strings is a fundamental string manipulation problem frequently asked in engineering interviews. The objective is to identify the longest string of starting characters that is shared by every single word in an input array. If there is no common beginning, the algorithm returns an empty string "".

For example, given the input array ["flower", "flow", "flight"], the longest common prefix is "fl". If the input is ["dog", "racecar", "car"], there is no mutual starting string, resulting in "".

In production engineering, this pattern is widely utilized:

• Trie-based Search Suggestions: Used to compute search auto-completions as a user types query characters.
• Network Routing: Used in CIDR IP address prefix matching to determine the longest matching route destination.
• Command Line Autocompleters: Resolves shared characters across available executable names when a user presses Tab.

Solving the Problem

1. Horizontal Scanning (Pairwise Reduction)

We designate the first string as our initial candidate prefix. We compare it against the second string, trimming characters off the end of the candidate until it matches. We then carry this reduced candidate to compare against the third string, repeating until the array is exhausted. While straightforward, this requires comparing many words repeatedly.

2. Vertical Scanning (Column-by-Column Comparison)

We align all strings in a grid and compare characters column-by-column, starting at index 0. If all characters in the column match, we proceed to index 1. The moment we encounter a mismatch or reach the end of any string, the loop breaks, and we return the checked substring.

3. Sorting First and Last (Lexicographical Boundaries)

By sorting the array lexicographically (O(n log n * m) time, where m is the string length), the first string strs[0] and the last string strs[strs.length - 1] will be the most distinct. We then perform a simple two-pointer traversal, comparing characters of only these two strings from left to right. The matching sequence is guaranteed to be the longest common prefix for the entire collection.

Detailed Trace Walkthrough

Let's trace this boundary sorting algorithm on the array strs = ["flower", "flow", "flight"]:

1. Step 1 (Base Case Check): We check if the array is null or empty. It is not.
2. Step 2 (Sorting): We sort the array alphabetically:
   • ["flower", "flow", "flight"] → ["flight", "flow", "flower"].
3. Step 3 (Extract Boundaries):
   • First string: first = "flight"
   • Last string: last = "flower"
4. Step 4 (Character Comparison): We iterate and compare characters of first and last starting at index 0:
   • Index 0: first.charAt(0) ('f') == last.charAt(0) ('f'). Match.
   • Index 1: first.charAt(1) ('l') == last.charAt(1) ('l'). Match.
   • Index 2: first.charAt(2) ('i') == last.charAt(2) ('o'). Mismatch!
5. Step 5 (Completion): The loop breaks at index 2. We return the substring of first from index 0 to 2, which is "fl".

Code Walkthrough

The key highlights of our Java implementation:

• Arrays.sort(strs); sorts the array, placing the most lexicographically distinct strings at positions 0 and strs.length - 1.
• while (i < first.length() && i < last.length()) prevents index out of bounds exceptions on empty or short boundary strings.
• first.substring(0, i) extracts the matched prefix cleanly using the pointer offset.

Implementation in Java

Below is the complete Java implementation featuring both the horizontal scanning and the optimized sorting boundary algorithm, along with a main method for trace logging.

package io.practise.dsa;
 
import java.util.Arrays;
 
public class LongestCommonPrefix {
 
    // Brute Force - O(n * m) where m is length of first word
    public String longestCommonPrefixBrute(String[] strs) {
        if (strs == null || strs.length == 0) return "";
        String prefix = strs[0];
        for (int i = 1; i < strs.length; i++) {
            while (strs[i].indexOf(prefix) != 0) {
                prefix = prefix.substring(0, prefix.length() - 1);
            }
        }
        return prefix;
    }
 
    // Optimized - O(n log n) via sorting first/last
    public String longestCommonPrefix(String[] strs) {
        if (strs.length == 0) return "";
        Arrays.sort(strs);
        String first = strs[0], last = strs[strs.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) {
        LongestCommonPrefix solver = new LongestCommonPrefix();
        String[] strs = {"flower", "flow", "flight"};
 
        System.out.println("--- Longest Common Prefix Demonstration ---");
        System.out.println("Input words: " + Arrays.toString(strs));
 
        String prefix = solver.longestCommonPrefix(strs);
        System.out.println("Longest Common Prefix: " + prefix);
    }
}

Conclusion & Takeaways

Solving the Longest Common Prefix problem highlights how we can leverage lexicographical sorting constraints to reduce element comparison pools. By sorting the array and inspecting only the boundary conditions, we convert an $O(n)$ comparative scan into a simple $O(1)$ string pointer iteration.