Find Longest Common Prefix in an Array

When dealing with string processing problems in Java, a common interview question is to find the longest common prefix among an array of strings. In this article, we will discuss an efficient approach to solve this problem using Java.

Problem Statement:

Given an array of strings, write a Java program to find the longest common prefix among all the strings. If there is no common prefix, return an empty string "".

Approach to Solve the Problem

1. Initialize the Prefix: Assume the first string is the prefix.
2. Compare with Other Strings: Iterate through the remaining strings and check if they start with the assumed prefix. If not, shorten the prefix one character at a time.
3. Return the Final Prefix: If the prefix becomes empty, return an empty string "", meaning there is no common prefix.

Java program to find the longest common prefix in an Array

Here’s the Java code to implement the above approach:

package com.javacodepoint.stringarray;

public class LongestCommonPrefix {
	
	// Method to find the longest common prefix among all strings in an array
	public static String findLongestCommonPrefix(String[] words) {
		if (words == null || words.length == 0) {
			return "";
		}

		String prefix = words[0];

		for (int i = 1; i < words.length; i++) {
			while (words[i].indexOf(prefix) != 0) {
				prefix = prefix.substring(0, prefix.length() - 1);
				if (prefix.isEmpty()) {
					return "";
				}
			}
		}
		return prefix;
	}

	public static void main(String[] args) {
		// Example array of strings
		String[] words = { "flower", "flow", "flight" };

		// Find and print the longest common prefix
		String longestPrefix = findLongestCommonPrefix(words);
		System.out.println("Longest Common Prefix: " + longestPrefix);
	}
}

OUTPUT:
Longest Common Prefix: fl

Code Explanation:

1. findLongestCommonPrefix()
   • Initializes the prefix as the first string in the array.
   • Iterates through the remaining strings, reducing the prefix if necessary.
2. indexOf(prefix) != 0
   • If the prefix is not found at the start of the current string, it is shortened.
3. Loop Continues Until the Prefix Matches All Strings
   • If no common prefix is found, return an empty string "".

Alternative Approach (Using Sorting)

In this approach, sort the array of strings and then compare only the first and last string in the sorted array.

import java.util.Arrays;

public class LongestCommonPrefixSorted {
    public static String findPrefix(String[] words) {
        if (words == null || words.length == 0) return "";

        Arrays.sort(words);
        String first = words[0];
        String last = words[words.length - 1];

        int i = 0;
        while (i < first.length() && first.charAt(i) == last.charAt(i)) {
            i++;
        }
        return first.substring(0, i);
    }
}

Conclusion

This article presented an efficient character-by-character matching approach to finding the longest common prefix in an array of strings. We also explored an alternative sorting-based solution. Mastering such problems enhances string manipulation skills, a key area for Java interviews.

You can learn the Top 20 string array programs for interview preparation (Click here).