Longest Common Prefix

Java coding interview problem for String Coding: Longest Common Prefix.

Finding the Longest Common Prefix (LCP) is one of the most popular String interview questions.

It appears in coding interviews because it tests multiple programming concepts, including:

String Manipulation
Arrays
Character Comparison
Loops
Trie (Prefix Tree)
Divide and Conquer
Time Complexity Analysis

Interviewers often ask several variations of this problem, such as:

Find the common prefix among multiple strings.
Find the longest common suffix.
Implement using Trie.
Solve without sorting.
Optimize for very large datasets.

Understanding multiple approaches prepares you for all these interview variations.

Problem Statement

Given an array of strings, return the longest common prefix shared by all strings.

If no common prefix exists, return an empty string.

Example 1

Input

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

Output

fl

Example 2

Input

["dog","racecar","car"]

Output

""

There is no common prefix.

Example 3

Input

["interview","internet","internal"]

Output

inter

Example 4

Input

["java","java","java"]

Output

java

What is Longest Common Prefix?

A prefix is the beginning part of a string.

Example

Programming

Prefixes

P

Pr

Pro

Prog

Progr

...

Given multiple strings,

the Longest Common Prefix is the longest starting substring shared by every string.

Example

flower

flow

flight

Common Prefixes

f

fl

Result

fl

Another Example

apple

application

apply

Common Prefix

appl

Output

appl

Why is this Question Asked in Interviews?

This problem evaluates whether candidates understand:

Array Traversal
Character Comparison
Nested Loops
String APIs
Trie Data Structure
Divide and Conquer
Time Complexity

It is also the foundation for many advanced interview questions.

Examples include:

Trie Implementation
Auto Complete
Search Suggestions
Longest Common Suffix
Prefix Matching

Real-World Applications

Finding common prefixes has many practical applications.

Search Engines

Search engines use prefixes while providing auto-complete suggestions.

IDE Auto Completion

Editors such as IntelliJ IDEA and VS Code suggest symbols using prefix matching.

Dictionary Applications

Word lookup becomes faster using prefixes.

File Systems

Common directory prefixes help optimize storage and searching.

DNA Sequence Analysis

Bioinformatics tools identify common genetic prefixes among DNA sequences.

Understanding Prefixes

Suppose we have

SpringBoot

Possible prefixes

S

Sp

Spr

Spri

Sprin

Spring

SpringB

SpringBo

...

Notice

A prefix always starts from index 0.

Prefix vs Suffix

Many beginners confuse prefixes and suffixes.

Prefix

Beginning of a string.

Programming

↓

Prog

Suffix

Ending of a string.

Programming

↓

ming

Example

Programming

Type	Example
Prefix	Prog
Suffix	ming

Mathematical Concept

Suppose

flower

flow

flight

Character Comparison

f == f == f

↓

l == l == l

↓

o != i

Stop immediately.

Longest Common Prefix

fl

Visual Representation

Input

flower

flow

flight

Comparison

flower

flow

flight

f ✓

↓

l ✓

↓

o ✗

Result

fl

Dry Run

Input

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

Initially

Prefix = flower

Compare

flower

flow

New Prefix

flow

Common Prefix

flow

Compare with

flight

Characters

f ✓

l ✓

o ✗

Final Result

fl

Approach 1 — Horizontal Scanning (Recommended)

Horizontal Scanning is the easiest and most commonly used interview solution.

The idea is simple:

Assume the first string is the common prefix.
Compare it with every remaining string.
Keep reducing the prefix until every string starts with it.

Algorithm

Assume the first string is the prefix.
Compare it with the next string.
Remove the last character until both match.
Repeat for all strings.
Return the final prefix.

Java Program

public class LongestCommonPrefix {

    public static String longestCommonPrefix(String[] words) {

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

        String prefix = words[0];

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

            while (!words[i].startsWith(prefix)) {

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

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

            }

        }

        return prefix;

    }

    public static void main(String[] args) {

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

        System.out.println(longestCommonPrefix(words));

    }

}

Output

fl

Step-by-Step Code Explanation

Check whether the array is empty.

if (words == null || words.length == 0)

Return

""

Assume the first string is the prefix.

String prefix = words[0];

Compare with every remaining string.

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

Reduce the prefix.

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

Continue until

startsWith(prefix)

becomes true.

Return the final prefix.

return prefix;

Dry Run of Horizontal Scanning

Input

["interview","internet","internal"]

Iteration	Current Prefix	Current Word	Updated Prefix
1	interview	internet	inter
2	inter	internal	inter

Output

inter

Advantages

Very easy to understand.
Clean implementation.
Excellent interview solution.
Requires no extra data structures.

Drawbacks

May repeatedly shrink the prefix.
Can perform unnecessary comparisons for large datasets.

Approach 2 — Vertical Scanning

Instead of comparing entire strings,

Vertical Scanning compares characters column by column.

Example

flower

flow

flight

Compare

Column 1

f

f

f

✓

Column 2

l

l

l

✓

Column 3

o

o

i

✗

Stop immediately.

Result

fl

Algorithm

Traverse characters of the first string.
Compare the same index in every other string.
If characters differ, return the substring up to that index.
Otherwise continue.

Java Program

public class LongestCommonPrefixVertical {

    public static String longestCommonPrefix(String[] words) {

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

        for (int i = 0; i < words[0].length(); i++) {

            char current = words[0].charAt(i);

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

                if (i == words[j].length()
                        || words[j].charAt(i) != current) {

                    return words[0].substring(0, i);

                }

            }

        }

        return words[0];

    }

    public static void main(String[] args) {

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

        System.out.println(longestCommonPrefix(words));

    }

}

Output

fl

Step-by-Step Code Explanation

Traverse every character of the first string.

for (int i = 0; i < words[0].length(); i++)

Store the current character.

char current = words[0].charAt(i);

Compare the same position in every string.

words[j].charAt(i)

If characters differ,

return

words[0].substring(0, i)

If every comparison succeeds,

return the first string.

Time & Space Complexity

Approach	Time	Extra Space
Horizontal Scanning	O(n × m)	O(1)
Vertical Scanning	O(n × m)	O(1)

Where:

n = number of strings
m = length of the shortest string

Comparison of Approaches

Feature	Horizontal Scanning	Vertical Scanning
Easy to Understand	⭐⭐⭐⭐⭐	⭐⭐⭐⭐
Interview Friendly	⭐⭐⭐⭐⭐	⭐⭐⭐⭐⭐
Extra Space	O(1)	O(1)
Performance	⭐⭐⭐⭐	⭐⭐⭐⭐⭐

Advantages

Both approaches require constant extra space.
Horizontal Scanning is straightforward and beginner-friendly.
Vertical Scanning can terminate early when characters differ.
Both are commonly accepted in coding interviews.

Drawbacks

Both approaches compare characters repeatedly.
Performance may degrade for very large collections of long strings.
More advanced approaches such as Sorting, Divide and Conquer, or Trie may be preferable for specialized use cases.

In Part 2, we'll cover:

Approach 3 – Sorting
Approach 4 – Divide and Conquer
Approach 5 – Trie (Prefix Tree)
Handling Empty Strings
Unicode Considerations
Comparison of All Approaches
Common Interview Mistakes
Edge Cases
Interview Follow-up Questions
Related Problems
Key Takeaways
Frequently Asked Interview Questions
Interview Tips

Approach 3 — Using Sorting

Another elegant approach is to sort the array of strings.

After sorting:

The first string becomes the lexicographically smallest.
The last string becomes the lexicographically largest.

The longest common prefix of the entire array must also be the common prefix of these two strings.

Why Does This Work?

Example

flower

flow

flight

Sorted

flight

flow

flower

Only compare

flight

flower

Common Prefix

fl

That is also the answer for the complete array.

Algorithm

Sort the array.
Compare the first and last strings.
Traverse characters until they differ.
Return the common prefix.

Java Program

import java.util.Arrays;

public class LongestCommonPrefixSorting {

    public static String longestCommonPrefix(String[] words) {

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

        Arrays.sort(words);

        String first = words[0];
        String last = words[words.length - 1];

        int index = 0;

        while (index < first.length()
                && index < last.length()
                && first.charAt(index) == last.charAt(index)) {

            index++;

        }

        return first.substring(0, index);

    }

    public static void main(String[] args) {

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

        System.out.println(longestCommonPrefix(words));

    }

}

Output

fl

Advantages

Easy implementation.
Simple logic.
Good interview discussion.

Drawbacks

Sorting takes additional time.
Slower than scanning approaches.

Approach 4 — Using Divide and Conquer

This approach applies the Divide and Conquer strategy.

Instead of comparing every string together,

split the array into two halves.

Find the common prefix of each half.

Merge the results.

Visualization

Input

flower

flow

flight

flame

Divide

            All Strings
           /           \
      Left Half      Right Half
      /      \        /       \
 flower     flow   flight   flame

Merge

flower

flow

↓

flow

flight

flame

↓

fl

Final

flow

fl

↓

fl

Algorithm

Divide the array into halves.
Recursively find prefixes.
Compare both prefixes.
Return the common portion.

Java Program

public class LongestCommonPrefixDivideConquer {

    public static String longestCommonPrefix(String[] words) {

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

        return divide(words, 0, words.length - 1);

    }

    private static String divide(String[] words, int left, int right) {

        if (left == right) {
            return words[left];
        }

        int mid = (left + right) / 2;

        String leftPrefix = divide(words, left, mid);
        String rightPrefix = divide(words, mid + 1, right);

        return commonPrefix(leftPrefix, rightPrefix);

    }

    private static String commonPrefix(String first, String second) {

        int length = Math.min(first.length(), second.length());

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

            if (first.charAt(i) != second.charAt(i)) {
                return first.substring(0, i);
            }

        }

        return first.substring(0, length);

    }

    public static void main(String[] args) {

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

        System.out.println(longestCommonPrefix(words));

    }

}

Output

fl

Advantages

Demonstrates recursion.
Excellent divide-and-conquer example.
Frequently discussed in system-level interviews.

Drawbacks

More complex.
Recursive overhead.

Approach 5 — Using Trie (Prefix Tree)

A Trie is a tree-like data structure designed specifically for prefix-based searching.

It is heavily used in:

Search Engines
Auto Complete
Dictionaries
Spell Checkers

Trie Structure

Input

flower

flow

flight

Trie

(root)
   |
   f
   |
   l
  / \
 o   i
 |    \
 w     g
 |
 e
 |
 r

The common path is

f

↓

l

Answer

fl

Algorithm

Insert every string into the Trie.
Start from the root.
Continue while:
- exactly one child exists
- current node is not the end of a word
Collect characters.
Return the prefix.

Simplified Java Program

class TrieNode {

    TrieNode[] children = new TrieNode[26];

    boolean end;

}

public class LongestCommonPrefixTrie {

    private final TrieNode root = new TrieNode();

    public void insert(String word) {

        TrieNode current = root;

        for (char ch : word.toCharArray()) {

            int index = ch - 'a';

            if (current.children[index] == null) {
                current.children[index] = new TrieNode();
            }

            current = current.children[index];

        }

        current.end = true;

    }

}

Note: A complete Trie implementation also includes traversal logic to extract the longest common prefix. The insertion logic above illustrates the core interview concept while keeping the example concise.

Advantages

Excellent for prefix searching.
Scales well for repeated prefix queries.
Widely used in production systems.

Drawbacks

More memory.
More complex implementation.
Overkill for a single query.

Handling Empty Strings

Consider

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

Since one string is empty,

the answer is

""

Always check for empty strings before processing.

Unicode Considerations

Java strings support Unicode.

Examples

こんにちは

नमस्ते

😊Hello

The scanning and sorting approaches work for general Java strings because they compare char values.

However, if your application must correctly handle supplementary Unicode characters (such as many emoji), consider iterating over Unicode code points instead of individual char values.

Edge Cases

Input	Expected Output
`[]`	`""`
`[""]`	`""`
`["abc"]`	`abc`
`["abc","abc"]`	`abc`
`["dog","cat"]`	`""`
`["prefix","pre","prevent"]`	`pre`
`null`	Handle appropriately based on application requirements

Time & Space Complexity

Approach	Time	Extra Space
Horizontal Scanning	O(n × m)	O(1)
Vertical Scanning	O(n × m)	O(1)
Sorting	O(n log n × m)	O(1)*
Divide and Conquer	O(n × m)	O(log n)
Trie	O(total characters)	O(total characters)

Where:

n = number of strings
m = length of the shortest string

Note: The sorting approach may require additional implementation-dependent space inside the sorting algorithm, but the comparison logic itself uses constant extra space.

Comparison of All Approaches

Approach	Interview Friendly	Performance	Best Use Case
Horizontal Scanning	⭐⭐⭐⭐⭐	⭐⭐⭐⭐	General interviews
Vertical Scanning	⭐⭐⭐⭐⭐	⭐⭐⭐⭐⭐	Early mismatch detection
Sorting	⭐⭐⭐⭐	⭐⭐⭐	Simple implementation
Divide and Conquer	⭐⭐⭐⭐	⭐⭐⭐⭐	Recursion practice
Trie	⭐⭐⭐	⭐⭐⭐⭐⭐	Repeated prefix searches

Common Interview Mistakes

Mistake 1

Not checking for an empty array.

Wrong

words[0]

Correct

if (words == null || words.length == 0)

Mistake 2

Not handling empty strings.

Input

["","abc"]

Output

""

Mistake 3

Using nested loops unnecessarily.

Prefer Horizontal or Vertical Scanning.

Mistake 4

Forgetting that the prefix starts at index 0.

Example

Programming

Correct Prefix

Prog

Not

gram

Mistake 5

Not stopping when the first mismatch occurs.

Early termination improves efficiency.

Interview Follow-up Questions

Q1. Can you solve it without sorting?

Q2. Which solution is the most efficient?

Q3. How does a Trie solve this problem?

Q4. What is the time complexity?

Q5. How would you support Unicode?

Q6. How would you find the longest common suffix?

Q7. Can you implement it recursively?

Q8. Why does sorting work?

Q9. How would you optimize for millions of strings?

Q10. Where is Trie used in real-world systems?

Key Takeaways

The Longest Common Prefix is the longest starting substring shared by every string.
Horizontal Scanning is the most common interview solution because it is simple and efficient.
Vertical Scanning often stops earlier when characters differ.
Sorting reduces the problem to comparing the first and last strings after lexicographical sorting.
Divide and Conquer demonstrates recursive problem solving.
Trie is the preferred data structure for applications with frequent prefix queries, such as autocomplete systems.

Frequently Asked Interview Questions

Q1. Which approach is best for coding interviews?

Horizontal Scanning is usually the best choice because it is easy to explain, efficient, and requires constant extra space.

Q2. Why does sorting work?

After sorting, the first and last strings are the most different lexicographically.

Their common prefix is guaranteed to be the common prefix for the entire array.

Q3. When should I use a Trie?

Use a Trie when your application performs many prefix searches, such as:

Search suggestions
Dictionary lookups
Auto-complete
Spell checking

Q4. Can this problem be solved recursively?

Yes.

The Divide and Conquer approach recursively computes the common prefix of smaller groups before combining the results.

Q5. What is the fastest solution?

For a single query, Horizontal Scanning or Vertical Scanning is typically the preferred solution with O(n × m) time and O(1) extra space.

Interview Tip

If an interviewer asks:

"Find the Longest Common Prefix among multiple strings."

Start with the Horizontal Scanning approach because it is intuitive and widely accepted.

Then discuss other approaches:

Horizontal Scanning (most common)
Vertical Scanning (early mismatch detection)
Sorting (compare first and last strings)
Divide and Conquer (recursive solution)
Trie (optimized for repeated prefix lookups)

Finally, ask clarifying questions such as:

Can the array contain empty strings?
Are strings case-sensitive?
Should Unicode characters be supported?
Is this a one-time query or part of a system with frequent prefix searches?

Showing both the coding solution and the trade-offs between approaches demonstrates strong Java and algorithmic interview skills.