Longest Common Prefix in Java

Author:

In this tutorial, I will demonstrate how to find the longest common prefix among an array of strings in Java. This is a popular string-based coding interview question that helps you understand string comparison, array traversal, and prefix matching.

A prefix is a sequence of characters that appears at the beginning of a string. The longest common prefix is the longest sequence of characters shared by every string in a collection, starting from the first character.

For example, consider the strings "flower", "flow", and "flight". All three strings begin with "fl", so their longest common prefix is "fl".

In this tutorial, you will learn three approaches to solving this problem: vertical scanning, horizontal scanning, and sorting. I will explain each approach with complete Java programs, expected outputs, a step-by-step dry run, complexity analysis, and important edge cases.

1. Problem Statement

Write a Java program to find the longest common prefix among an array of strings.

If no common prefix exists, return an empty string.

Example 1: Common Prefix Exists

Input:
["flower", "flow", "flight"]

Output:
fl

Explanation: All three strings begin with the characters 'f' and 'l'. Their next characters are different, so the longest common prefix is "fl".

Example 2: No Common Prefix

Input:
["dog", "racecar", "car"]

Output:
""

The strings do not share any character at the beginning, so the result is an empty string.

Example 3: Identical Strings

Input:
["java", "java", "java"]

Output:
java

Since all three strings are identical, the entire string is their longest common prefix.

2. Understanding the Longest Common Prefix

Before implementing the program, it is important to understand the difference between a prefix and a substring.

A prefix always starts at the beginning of a string.

For example, consider the string "programming".

Some valid prefixes are:

  • p
  • pr
  • pro
  • prog
  • program
  • programming

However, "gram" is not a prefix because it does not begin at index 0.

When finding the longest common prefix, the program compares characters starting from the beginning of every string.

The comparison stops when:

  • Two characters at the same position are different.
  • One of the strings reaches its end.

3. Method 1: Longest Common Prefix Using Vertical Scanning

Vertical scanning is one of the simplest and most efficient approaches to this problem.

The algorithm takes the first string as a reference and compares each of its characters with the character at the same position in every other string.

If a mismatch occurs, the algorithm returns the common prefix identified so far.

How Vertical Scanning Works

  1. Check whether the input array is null or empty.
  2. Select the first string as a reference.
  3. Iterate through each character position in the reference string.
  4. Compare the character at that position with the corresponding character in every other string.
  5. If a string is too short or its character differs, return the prefix found so far.
  6. If all characters of the reference string match, return the entire reference string.

Java Program Using Vertical Scanning

public class LongestCommonPrefix {

    /**
     * Finds the longest common prefix
     * among an array of strings.
     *
     * @param strs input array of strings
     * @return longest common prefix
     */
    public static String longestCommonPrefix(String[] strs) {

        if (strs == null || strs.length == 0) {
            return "";
        }

        String first = strs[0];

        if (first == null) {
            return "";
        }

        // Compare each character of the first string
        for (int i = 0; i < first.length(); i++) {

            char currentChar = first.charAt(i);

            // Compare with all remaining strings
            for (int j = 1; j < strs.length; j++) {

                if (strs[j] == null
                        || i >= strs[j].length()
                        || strs[j].charAt(i) != currentChar) {

                    return first.substring(0, i);
                }
            }
        }

        return first;
    }

    public static void main(String[] args) {

        String[] strs = {"flower", "flow", "flight"};

        String result = longestCommonPrefix(strs);

        System.out.println(
                "Longest Common Prefix: " + result);
    }
}

Output

Longest Common Prefix: fl

This solution compares characters directly without sorting the input array or creating additional collections.

4. Step-by-Step Explanation of the Java Program

Step 1: Validate the Input Array

if (strs == null || strs.length == 0) {
    return "";
}

If the input array is null or contains no strings, the method returns an empty string.

Step 2: Select the First String

String first = strs[0];

The first string is used as the reference for comparisons.

Every common prefix must also be a prefix of the first string.

Therefore, the algorithm only needs to examine character positions within this string.

Step 3: Iterate Through the Reference String

for (int i = 0; i < first.length(); i++) {

    char currentChar = first.charAt(i);
}

The outer loop visits each character position in the first string.

For example, for "flower", the positions are:

Character: f l o w e r
Index:     0 1 2 3 4 5

Step 4: Compare the Character with Other Strings

for (int j = 1; j < strs.length; j++) {

The inner loop checks the same character position in every remaining string.

For example, at index 0:

flower -> f
flow   -> f
flight -> f

All characters match, so the program continues.

At index 1:

flower -> l
flow   -> l
flight -> l

Again, all characters match.

Step 5: Stop When a Mismatch Occurs

if (strs[j] == null
        || i >= strs[j].length()
        || strs[j].charAt(i) != currentChar) {

    return first.substring(0, i);
}

The condition checks whether:

  • The current string is null.
  • The current position is beyond the string's length.
  • The character at the current position differs from the reference character.

If any condition is true, the method returns the matching prefix.

For the strings "flower", "flow", and "flight", the mismatch occurs at index 2 because the characters are 'o', 'o', and 'i'.

Therefore, the method returns:

first.substring(0, 2)

The result is "fl".

Step 6: Return the Entire Reference String if All Characters Match

return first;

If the algorithm finishes without encountering a mismatch, the entire first string is a prefix of every other string.

5. Dry Run: Finding the Longest Common Prefix

Let's understand the algorithm with this input:

["flower", "flow", "flight"]

The program compares corresponding character positions in all three strings.

Index flower flow flight Result
0 f f f Match
1 l l l Match
2 o o i Mismatch

The program stops at index 2.

All characters before that position match, so the longest common prefix is:

fl

6. Method 2: Longest Common Prefix Using Horizontal Scanning

Horizontal scanning compares a candidate prefix with each string one by one.

The algorithm begins with the entire first string as the candidate prefix.

For each remaining string, it shortens the prefix until the string starts with that prefix.

Java Program Using Horizontal Scanning

public class LongestCommonPrefixHorizontal {

    public static String longestCommonPrefix(String[] strs) {

        if (strs == null || strs.length == 0) {
            return "";
        }

        String prefix = strs[0];

        if (prefix == null) {
            return "";
        }

        for (int i = 1; i < strs.length; i++) {

            if (strs[i] == null) {
                return "";
            }

            // Reduce prefix until the string starts with it
            while (!strs[i].startsWith(prefix)) {

                prefix = prefix.substring(
                        0, prefix.length() - 1);

                if (prefix.isEmpty()) {
                    return "";
                }
            }
        }

        return prefix;
    }

    public static void main(String[] args) {

        String[] strs = {
                "interview",
                "internet",
                "internal",
                "interval"
        };

        String result = longestCommonPrefix(strs);

        System.out.println(
                "Longest Common Prefix: " + result);
    }
}

Output

Longest Common Prefix: inter

How Horizontal Scanning Works

Initially, the candidate prefix is:

interview

The program compares this prefix with the next string, "internet".

Since "internet" does not start with "interview", the algorithm shortens the prefix until it finds a match.

The common prefix becomes "inter".

The remaining strings, "internal" and "interval", also start with "inter".

Therefore, the final result is "inter".

7. Method 3: Longest Common Prefix Using Sorting

Another approach is to sort the strings lexicographically.

After sorting, compare only the first and last strings.

Why does this work?

In lexicographical order, strings sharing a prefix appear together. The common prefix of the first and last strings is also a prefix of all strings between them.

For example, after sorting the strings "flower", "flow", and "flight", the array becomes:

[flight, flow, flower]

Comparing "flight" and "flower" gives the prefix "fl".

Java Program Using Sorting

import java.util.Arrays;

public class LongestCommonPrefixSorting {

    public static String longestCommonPrefix(String[] strs) {

        if (strs == null || strs.length == 0) {
            return "";
        }

        // Handle null elements explicitly
        for (String str : strs) {
            if (str == null) {
                return "";
            }
        }

        // Copy input to avoid modifying original array
        String[] sorted = Arrays.copyOf(
                strs, strs.length);

        Arrays.sort(sorted);

        String first = sorted[0];
        String last = sorted[sorted.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[] strs = {
                "flower",
                "flow",
                "flight"
        };

        String result = longestCommonPrefix(strs);

        System.out.println(
                "Longest Common Prefix: " + result);
    }
}

Output

Longest Common Prefix: fl

How the Sorting Approach Works

  1. Validate the input array.
  2. Create a copy of the array to preserve the original order.
  3. Sort the copied array using Arrays.sort().
  4. Select the first and last strings.
  5. Compare characters from the beginning of both strings.
  6. Return the matching prefix.

The sorting approach is concise and useful when the strings are already sorted or when sorting is part of a larger operation.

However, sorting the entire array introduces additional work that is unnecessary for this problem.

8. Time and Space Complexity

Let's compare the three approaches.

Assume:

  • n represents the number of strings.
  • m represents the maximum string length.
  • S represents the total number of characters across all strings.
Approach Time Complexity Additional Space Recommendation
Vertical scanning O(S) O(1) auxiliary Recommended
Horizontal scanning O(S) typical bound for prefix comparisons O(m) for prefix strings Good alternative
Sorting O(n × m × log n) worst-case comparison bound O(n) or more for sorting support Simple alternative

The space bounds exclude the returned substring unless stated otherwise.

Vertical Scanning Complexity

Vertical scanning compares character positions until it finds a mismatch or reaches the end of a string.

In the worst case, it examines all character positions of every string that could belong to the shared prefix.

Therefore, its running time is bounded by O(S).

The algorithm uses a few variables, so its auxiliary space complexity is O(1), excluding the returned substring.

Horizontal Scanning Complexity

Horizontal scanning repeatedly compares the current prefix with the next string.

The prefix becomes shorter as necessary, so the total work depends on the lengths of the strings and their shared prefixes.

Repeated substring creation also uses additional memory.

Sorting Complexity

Sorting requires comparing strings lexicographically.

Each string comparison can examine multiple characters, so sorting may require more work than directly scanning common prefixes.

For coding interviews, vertical scanning is generally the better starting point.

9. Handling Important Edge Cases

Case 1: Empty Array

Input:
[]

Output:
""

The program returns an empty string because the array contains no strings.

Case 2: Single String

Input:
["programming"]

Output:
programming

If the array contains one string, the entire string is its longest common prefix.

Case 3: No Common Prefix

Input:
["apple", "banana", "cherry"]

Output:
""

The first characters are different, so no common prefix exists.

Case 4: All Strings Are Identical

Input:
["java", "java", "java"]

Output:
java

Case 5: One String Is a Prefix of Another

Input:
["app", "apple", "application"]

Output:
app

The shortest string is itself a prefix of the other strings.

Case 6: One String Is Empty

Input:
["flower", "", "flow"]

Output:
""

If any string is empty, the longest common prefix is also empty.

Case 7: Uppercase and Lowercase Letters

Input:
["Java", "javascript", "javadoc"]

Output:
""

The provided implementations are case-sensitive. Therefore, uppercase 'J' and lowercase 'j' are different.

Case 8: Null Strings

The implementations return an empty string when the array contains a null element.

This is a deliberate design choice. You can change the behavior to throw an exception if null elements are considered invalid input.

10. Common Mistakes to Avoid

Mistake 1: Comparing Only the First Two Strings

A common mistake is finding the common prefix of the first two strings and returning it immediately.

The prefix must be shared by every string in the array.

Always compare the result with the remaining strings.

Mistake 2: Forgetting String Length Checks

Before accessing a character at index i, make sure that index exists in the current string.

Otherwise, the program may throw a StringIndexOutOfBoundsException.

Mistake 3: Confusing Prefix and Substring

A prefix must begin at index 0.

For example, "gram" appears inside "programming", but it is not a prefix.

Mistake 4: Ignoring Case Sensitivity

Java compares uppercase and lowercase characters as different values.

If your application requires case-insensitive prefix matching, normalize strings consistently before comparison.

Mistake 5: Sorting Without Considering Input Modification

The Arrays.sort() method modifies the array passed to it.

If you need to preserve the original array order, create a copy before sorting.

11. Frequently Asked Questions

Q1. What is the longest common prefix in Java?

It is the longest sequence of characters that appears at the beginning of every string in an array or collection.

Q2. What is the best way to find the longest common prefix in Java?

Vertical scanning is a simple and efficient approach. It compares characters at the same position across all strings and stops when a mismatch occurs.

Q3. What happens if no common prefix exists?

The method returns an empty string.

Q4. Can I solve this problem using sorting?

Yes. Sort the strings lexicographically and compare the first and last strings to determine the longest common prefix.

Q5. What is the time complexity of vertical scanning?

Its worst-case time complexity is O(S), where S is the total number of characters across all input strings.

Q6. What happens if all strings are identical?

The entire string is returned as the longest common prefix.

Q7. Does the algorithm work with strings of different lengths?

Yes. The comparison stops when the shortest relevant string ends or when a character mismatch occurs.

Q8. Is the longest common prefix problem case-sensitive?

The implementations in this tutorial are case-sensitive because they compare characters directly.

Q9. What is the difference between longest common prefix and longest common substring?

A longest common prefix must start at the beginning of every string. A longest common substring can occur at any position within the strings.

12. Conclusion

In this tutorial, you learned how to find the longest common prefix among strings in Java using three different approaches.

  • Vertical scanning: Compares corresponding character positions across all strings.
  • Horizontal scanning: Starts with a candidate prefix and shortens it when necessary.
  • Sorting: Sorts the strings and compares the first and last elements.

For Java coding interviews, I recommend practicing the vertical scanning approach first. It is efficient, straightforward, and does not require sorting or additional data structures.

Once you understand vertical scanning, explore the horizontal scanning and sorting approaches to strengthen your string-processing skills.

The same concepts are useful in other coding interview problems involving prefix matching, string comparison, and text processing.

13. Official Java Documentation

For additional information about the Java APIs used in this tutorial, refer to the official Oracle documentation:

Continue Learning with Java Guides

Want to take your programming skills to the next level? Explore my practical Udemy courses on Java, Spring Boot, Microservices, Full-Stack Development, Docker, and Generative AI. You can also follow my structured learning roadmaps to become a professional developer.

By Ramesh Fadatare - Udemy Instructor Partner

Comments

Post a Comment

Leave Comment