Longest Common Prefix problem and solution in Java and Python

The Longest Common Prefix problem is one of the most popular string problems in interviews. It looks simple but tests how you think about string traversal and edge cases efficiently.

Let’s go step-by-step 👇

---

🧩 Problem: Longest Common Prefix

Question

Given an array of strings, find the longest common prefix (LCP) among them. If there is no common prefix, return an empty string "".

---

Example 1

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

Example 2

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

✅ Explanation: There is no common starting substring.

---

🧠 Intuition

We’re looking for the common starting part shared by all strings.

Example:

flower
flow
flight
↓
Common characters:
f → ✅
l → ✅
o → ❌ (break)
=> "fl"

---

💡 Approach 1: Horizontal Scanning (Compare One by One)

🪜 Steps:

1. Assume the first string is the prefix.
2. Compare it with each next string.
3. Reduce prefix length until it matches.

---

✅ Java Solution

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;
    }
}

---

✅ Python Solution

def longestCommonPrefix(strs):
    if not strs:
        return ""

    prefix = strs[0]
    for s in strs[1:]:
        while not s.startswith(prefix):
            prefix = prefix[:-1]
            if not prefix:
                return ""
    return prefix

---

💡 Approach 2: Vertical Scanning (Character by Character)

Compare characters column-wise (like reading vertically).

✅ Python Example

def longestCommonPrefix(strs):
    if not strs:
        return ""
    
    for i in range(len(strs[0])):
        for s in strs[1:]:
            if i == len(s) or s[i] != strs[0][i]:
                return strs[0][:i]
    return strs[0]

---

💡 Approach 3: Divide and Conquer

Split array into halves → find LCP of each half → merge results. This works faster when many strings share partial prefixes.

---

✅ Java (Divide & Conquer)

class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) return "";
        return lcp(strs, 0, strs.length - 1);
    }

    private String lcp(String[] strs, int left, int right) {
        if (left == right) return strs[left];

        int mid = (left + right) / 2;
        String lcpLeft = lcp(strs, left, mid);
        String lcpRight = lcp(strs, mid + 1, right);
        return commonPrefix(lcpLeft, lcpRight);
    }

    private String commonPrefix(String left, String right) {
        int min = Math.min(left.length(), right.length());
        for (int i = 0; i < min; i++) {
            if (left.charAt(i) != right.charAt(i))
                return left.substring(0, i);
        }
        return left.substring(0, min);
    }
}

---

⚙️ Complexity

Operation	Time	Space
Horizontal / Vertical	O(S)	O(1)
Divide & Conquer	O(S)	O(log n)

Where S = total characters across all strings.

---

🧠 To Explain to a Kid

Imagine your friends are all saying words:

• "flower"
• "flow"
• "flight"

You listen to the beginning of each word and stop when they stop matching — that’s your common prefix 🎧🌸

---

🧩 Edge Cases

Input	Output	Explanation
[]	""	Empty list
["dog"]	"dog"	Only one string
["dog","doghouse"]	"dog"	Exact prefix match
["dog","cat"]	""	No common prefix

---

🧠 Bonus – Trie (Prefix Tree) Approach

A more advanced way is to build a Trie of all strings and find the longest path where all nodes have only one child — that’s the longest common prefix.

---