Find the Longest Common Prefix (Java)

Find the Longest Common Prefix (Java)

In this post, we will learn how to find the longest common prefix (LCP) among an array of strings. This is a common string manipulation problem often asked in coding interviews.

---

Problem Statement

Given an array of strings, find the longest prefix string that is common to all strings. If there is no common prefix, return an empty string.

Examples:

["flower","flow","flight"] → "fl"
["dog","racecar","car"] → ""
["interview","internet","internal"] → "inte"

---

Approach Used

• Take the first string as the initial prefix
• Compare it with each string in the array
• If the current string does not start with the prefix, shorten the prefix
• Repeat until the prefix fits all strings

---

Java Code Implementation

public class LongestCommonPrefix {

    public static void main(String[] args) {

        String[][] testCases = {
            {"flower","flow","flight"},
            {"dog","racecar","car"},
            {"interview","internet","internal"},
            {"apple","app","april"}
        };

        for(String[] arr : testCases){
            System.out.print("Strings: ");
            for(String s: arr) System.out.print(s + " ");
            System.out.println("\nLongest Common Prefix: " + longestCommonPrefix(arr));
            System.out.println();
        }
    }

    private static String longestCommonPrefix(String[] str) {

        if(str == null || str.length == 0) return "";

        String prefix = str[0];

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

        return prefix;
    }
}

---

Explanation

Step-by-Step Approach

• Assume the first string is the longest prefix initially
• Compare with each string in the array
• If the current string does not start with the prefix, remove the last character of the prefix
• Continue until the prefix is common to all strings

Technique Used: Iterative Prefix Trimming

---

Sample Output

Strings: flower flow flight 
Longest Common Prefix: fl

Strings: dog racecar car 
Longest Common Prefix: 

Strings: interview internet internal 
Longest Common Prefix: inte

Strings: apple app april 
Longest Common Prefix: ap

---

Time & Space Complexity

Metric	Complexity
Time	O(N * M)
Space	O(1)

---

Interview Tip

In interviews, this approach is preferred for its simplicity. For large datasets, Trie-based solutions can optimize prefix lookup.

---

Want to Practice More?

• Find Longest Common Prefix using Divide and Conquer
• Implement LCP using Trie data structure
• Case-insensitive LCP

---

Category: Strings
Difficulty: Easy / Medium
Technique: Iterative, Prefix Trimming