LeetCode #14: Longest Common Prefix in Java | Simple Vertical Scanning Approach

Given an array of strings, find the longest common prefix among all the strings.
If there is no common prefix, return an empty string "".
Example:

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

Hello everyone! 👋

Let's solve the Longest Common Prefix problem.

Before solving the problem, we should understand it first. There are multiple ways to solve this problem. Some approaches are :

1. Vertical scanning
2. Trie-based approach
3. Horizontal scanning
4. Divide and conquer

For this problem, I will use the vertical Scanning approach because it is easier to understand and implement.

What is vertical scanning?

Vertical scanning means comparing the character/element at the same
index position across multiple strings.

String 1: C A R
String 2: C A T
String 3: C A N

Now compare the characters vertically.

Index 0 → C, C, C
Index 1 → A, A, A
Index 2 → R, T, N

At index 0:

C = C = C ✓

At index 1:

A = A = A ✓

At index 2:

R ≠ T ≠ N ✗

So we stop at index 2.

The common prefix is:

"CA"

This is why it is called vertical scanning — we compare characters at the same index across different strings.

- Let's Understand the Algorithm

Now let's understand the algorithm step by step:

1. Take the first string as a reference
2. Traverse the reference string character by character.
3. Compare the current character with the character at the same index in all remaining strings.
4. If any character does not match, stop comparing.
5. If we reach the end of any string, stop comparing.
6. If all characters match, continue to the next index.
7. Repeat this process until a mismatch occurs or the end of a string is reached.
8. Return the characters matched so far as the longest common prefix.

For example:
Suppose we have:
["flower", "flow", "flight"]

Index 0 → f = f = f ✓
Index 1 → l = l = l ✓
Index 2 → o = o = i ✗
At index 2, the characters do not match, so we stop.
Therefore, the longest common prefix is: "fl"

Java Implementation

class Main {

    public static String longestCommonPrefix(String[] strs) {

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

        String firstS = strs[0];

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

            char ch = firstS.charAt(i);

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

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

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

        return firstS;
    }

    public static void main(String[] args) {

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

        String result = longestCommonPrefix(strs);

        System.out.println(result);
    }
}

Understanding the Code >>>>>>>>>>>>>>>>>

Now let's understand the code line by line.
1. Check for an Empty Input
if (strs == null || strs.length == 0) { return ""; }

First, we check whether the input array is:

null
empty

If there are no strings to compare, there cannot be a common prefix.

Therefore, we return: ""

2. Take the First String as Reference
String firstS = strs[0];

Here, we use the first string as our reference.

For:

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

we get:

firstS = "flower"

We will use "flower" to decide which character we are currently checking.

3. Traverse the Reference String
for (int i = 0; i < firstS.length(); i++) {

This loop goes through the reference string character by character.

For "flower":

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

So i will be:

0 → 1 → 2 → 3 → 4 → 5

4. Get the Current Character
char ch = firstS.charAt(i);

At every index, we get the current character from the reference string.

For example, when:

i = 0

we get:

ch = 'f'

When:

i = 1

we get:

ch = 'l'

5. Compare With the Remaining Strings
for (int j = 1; j < strs.length; j++) {

We start j from 1 because index 0 is already our reference string.

For:

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

we compare with:

strs[1] → "flow"
strs[2] → "flight"

The first condition checks whether we have reached the end of the current string.

6. Check Two Conditions
if (i >= strs[j].length()
|| strs[j].charAt(i) != ch) {

There are two important conditions here.

Condition 1: String Has Ended
i >= strs[j].length()

This checks whether we have reached the end of the current string.

For example:

"flow"
0123

If:

i = 4

then there is no character at index 4.

So we stop.

Condition 2: Character Does Not Match
strs[j].charAt(i) != ch

This checks whether the character at the same index is different.

For example:

flower → o
flow → o
flight → i

Here:

'o' != 'i'

So the condition becomes true.

7. Return the Common Prefix

If either condition is true:

return firstS.substring(0, i);

we return the characters matched before index i.

For example, if the mismatch occurs at index 2:

flower
012345
↑
index 2

We call:

firstS.substring(0, 2)

In Java, the second index is exclusive.

So:

substring(0, 2)

returns:

"fl"

It includes:

index 0 → f
index 1 → l

but does not include:

index 2 → o

Therefore:

"fl"

is our longest common prefix.

Time Complexity

Let's understand the time complexity.
n = number of strings
m = length of the reference string
In the worst case, we may check m characters across n strings.
So the time complexity is:
O(n × m)

Space Complexity

The space complexity is: O(1). Why?
Because we are not creating an extra array or storing all the characters being compared.
We only use a few variables such as:
String firstS
char ch
int i
int j
The input strings are already given to us, so we don't count them as extra space.

Therefore:
Space Complexity: O(1)