Algorithm Day109 - Longest Common Prefix

Posted on In Views:

📌 Problem

Write a function to find the longest common prefix string amongst an array of strings.
If there is no common prefix, return an empty string "".

💬 Examples

Example 1

1
2
Input: strs = ["flower","flow","flight"]
Output: "fl"

Example 2

1
2
Input: strs = ["dog","racecar","car"]
Output: ""

Explanation: There is no common prefix among the input strings.

💡 Intuition

A common and simple approach is to start from the first string as the prefix, and then gradually shorten it while checking against other strings.
Stop when the prefix no longer matches.

🔢 Java Code (Vertical Scanning)

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) return "";
        String prefix = strs[0];
        for (int i = 1; i < strs.length; i++) {
            while (strs[i].indexOf(prefix) != 0) {
                prefix = prefix.substring(0, prefix.length() - 1);
                if (prefix.isEmpty()) return "";
            }
        }
        return prefix;
    }
}

⏱ Complexity Analysis

  • Time: O(S) — S = total number of characters in all strings (each char checked at most once).
  • Space: O(1) — no extra data structure used.

✍️ Summary

  • Start with the first string as prefix and reduce it when mismatches occur.
  • Efficient for small/medium input sizes.
  • A clean and intuitive string problem that often appears early in interviews.