DEV Community

Jaspreet singh
Jaspreet singh

Posted on

Longest Common Prefix | String Traversal

#algorithms #beginners #interview #java
leetcode.com

Problem Statement

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

If there is no common prefix, return an empty string.

Brute Force Intuition

In an interview, you can explain it like this:

Compare every pair of strings character by character and keep reducing the common prefix.

This repeatedly compares characters across multiple strings.

Complexity

  • Time Complexity: O(N × M)
  • Space Complexity: O(1)

Where:

  • N = Number of strings
  • M = Length of the shortest string

Brute Force Code 

class Solution {

    public String longestCommonPrefix(String[] strs) {

        String prefix = strs[0];

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

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

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

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

        return prefix;
    }
}
Enter fullscreen mode Exit fullscreen mode

Moving Towards the Optimal Approach

Instead of comparing every pair,

observe that:

The longest common prefix
cannot be longer than
the shortest string.
Enter fullscreen mode Exit fullscreen mode

So,

take the first string as reference.

Compare every character at the same position across all strings.

The first mismatch ends the answer.

Pattern Recognition

Whenever you see:

  • Common Prefix
  • Compare Multiple Strings
  • Character-by-Character Matching

Think:

Vertical Scanning

Key Observation

Suppose:

flower

flow

flight
Enter fullscreen mode Exit fullscreen mode

Compare:

f ✓

l ✓

o ✗
Enter fullscreen mode Exit fullscreen mode

Stop immediately.

Answer:

fl
Enter fullscreen mode Exit fullscreen mode

Optimal Approach

Take:

First String
Enter fullscreen mode Exit fullscreen mode

For every character:

Compare it with the corresponding character in every other string.

If:

  • Character differs
  • String ends

Return prefix till previous index.

Optimal Java Solution 

class Solution {

    public String longestCommonPrefix(String[] strs) {

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

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

            char ch = strs[0].charAt(i);

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

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

                    return strs[0].substring(0, i);
                }
            }
        }

        return strs[0];
    }
}
Enter fullscreen mode Exit fullscreen mode

Dry Run

Input 

["flower","flow","flight"]
Enter fullscreen mode Exit fullscreen mode

Compare:

f

↓

All Match ✓
Enter fullscreen mode Exit fullscreen mode

Compare:

l

↓

All Match ✓
Enter fullscreen mode Exit fullscreen mode

Compare:

o

↓

flight has i

Mismatch ✗
Enter fullscreen mode Exit fullscreen mode

Answer:

fl
Enter fullscreen mode Exit fullscreen mode

Why Vertical Scanning Works?

All strings must share the same character at the same index.

The first mismatch immediately tells us that the common prefix cannot continue further.

Since every character is checked at most once across all strings, the solution is efficient.

Complexity Analysis

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

Where:

  • N = Number of strings
  • M = Length of the shortest string

Interview One-Liner

Use the first string as a reference and compare each character vertically across all strings until the first mismatch.

Pattern Learned 

Multiple Strings

↓

Compare Same Index

↓

Stop at First Mismatch
Enter fullscreen mode Exit fullscreen mode

Similar Problems

  • Longest Common Prefix
  • Shortest Common Supersequence
  • Longest Common Subsequence
  • Implement strStr()
  • Group Anagrams

Memory Trick

Think:

Take First String

↓

Compare Column-wise

↓

Mismatch?

↓

Return Prefix
Enter fullscreen mode Exit fullscreen mode

Mental Model 

flower

flow

flight

↓

Vertical Scan

↓

Common Prefix
Enter fullscreen mode Exit fullscreen mode

Whenever you hear:

"Longest Common Prefix"

your brain should immediately think:

Vertical Character Scanning

Top comments (0)