8. Longest Common Prefix

🔗 LeetCode Problem: 14. Longest Common Prefix
📊 Difficulty: Easy
🏷️ Topics: String, Array

Problem Statement

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 "".

Example 1:

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

Example 2:

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

Constraints: - 1 <= strs.length <= 200 - 0 <= strs[i].length <= 200 - strs[i] consists of only lowercase English letters

---

Quick Revision Notes

🎯 Core Concept:

Find the leftmost characters that are identical across ALL strings. The moment any string disagrees, we stop.

⚡ Quick Implementation:

// Horizontal Scanning - Most Intuitive
public String longestCommonPrefix(String[] strs) {
    if (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;
}

🔑 Key Insights:

• Common prefix cannot be longer than shortest string
• If any string is empty, result must be empty
• Can scan vertically (by position) or horizontally (by string)
• indexOf(prefix) == 0 checks if string starts with prefix

🎪 Memory Aid:

"Line up strings vertically, scan columns until mismatch!"
Think: "Check position-by-position OR reduce-and-check"

---

🎨 Visual Understanding

The Problem Visualized

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

Vertical View (Column-by-Column):
Position:  0   1   2   3   4   5
          ┌───┬───┬───┬───┬───┬───┐
flower:   │ f │ l │ o │ w │ e │ r │
          ├───┼───┼───┼───┼───┼───┤
flow:     │ f │ l │ o │ w │   │   │
          ├───┼───┼───┼───┼───┼───┤
flight:   │ f │ l │ i │ g │ h │ t │
          └───┴───┴───┴───┴───┴───┘
           ✓   ✓   ✗

Column 0: All have 'f' → Include ✓
Column 1: All have 'l' → Include ✓
Column 2: 'o','o','i' → Mismatch! Stop ✗

Result: "fl"

Horizontal Reduction Visualized

Start: prefix = "flower"

Compare with "flow":
  "flower" in "flow"? No → trim
  "flowe"  in "flow"? No → trim  
  "flow"   in "flow"? Yes ✓

Compare with "flight":
  "flow"   in "flight"? No → trim
  "flo"    in "flight"? No → trim
  "fl"     in "flight"? Yes ✓

Final: "fl"

---

🎯 Approach 1: Vertical Scanning

The Most Natural Thinking 💭

Core Logic:

Scan position-by-position (column-by-column)
For each position i:
  - Get character from first string at position i
  - Check if ALL other strings have same character at position i
  - If any string too short OR character differs → STOP, return prefix so far

Why This Works: - Directly models the question: "How far can we go before mismatch?" - Easy to visualize as scanning columns top-to-bottom - Natural stopping point when disagreement found

Implementation

public String longestCommonPrefix(String[] strs) {
    if (strs == null || strs.length == 0) return "";

    // Scan each character position
    for (int i = 0; i < strs[0].length(); i++) {
        char c = strs[0].charAt(i);  // Reference character

        // Check this character in all other strings
        for (int j = 1; j < strs.length; j++) {
            // Two stop conditions:
            // 1. String j too short (i out of bounds)
            // 2. Character at position i doesn't match
            if (i >= strs[j].length() || strs[j].charAt(i) != c) {
                return strs[0].substring(0, i);
            }
        }
    }

    // Entire first string is common prefix
    return strs[0];
}

Step-by-Step Execution: strs = ["flower", "flow", "flight"]

Position i=0, char='f':
├─ Check "flow"[0] = 'f'   ✓ Match
├─ Check "flight"[0] = 'f' ✓ Match
└─ Continue to position 1

Position i=1, char='l':
├─ Check "flow"[1] = 'l'   ✓ Match
├─ Check "flight"[1] = 'l' ✓ Match
└─ Continue to position 2

Position i=2, char='o':
├─ Check "flow"[2] = 'o'   ✓ Match
├─ Check "flight"[2] = 'i' ✗ MISMATCH!
└─ Return substring(0,2) = "fl"

Result: "fl"

⏰ Time: O(S) where S = sum of all characters
💾 Space: O(1)

---

✅ Approach 2: Horizontal Scanning (Optimal)

The Reduction Strategy 💡

Core Logic:

Start: prefix = first string (optimistic assumption)

For each remaining string:
  While current string doesn't start with prefix:
    - Remove last character from prefix
    - If prefix becomes empty → return ""

Return final prefix

Why This Works: - Prefix can only get shorter, never longer → guaranteed progress - Naturally handles all edge cases through reduction - indexOf(prefix) == 0 efficiently checks "starts with"

Implementation

public String longestCommonPrefix(String[] strs) {
    if (strs == null || strs.length == 0) return "";

    String prefix = strs[0];  // Start optimistic

    for (int i = 1; i < strs.length; i++) {
        // Reduce prefix until it fits
        while (strs[i].indexOf(prefix) != 0) {
            prefix = prefix.substring(0, prefix.length() - 1);
            if (prefix.isEmpty()) return "";
        }
    }

    return prefix;
}

Step-by-Step Execution: strs = ["flower", "flow", "flight"]

Initial: prefix = "flower"

Compare with "flow":
├─ "flow".indexOf("flower") = -1 (not found)
├─ Trim: prefix = "flowe"
├─ "flow".indexOf("flowe") = -1
├─ Trim: prefix = "flow"
├─ "flow".indexOf("flow") = 0 ✓ Found!
└─ prefix = "flow"

Compare with "flight":
├─ "flight".indexOf("flow") = -1
├─ Trim: prefix = "flo"
├─ "flight".indexOf("flo") = -1
├─ Trim: prefix = "fl"
├─ "flight".indexOf("fl") = 0 ✓ Found!
└─ prefix = "fl"

Result: "fl"

⏰ Time: O(S) where S = sum of all characters
💾 Space: O(1)

---

🔍 Edge Cases

Case 1: Single string
Input: ["hello"]
Output: "hello"
Reason: Entire string is trivially common to itself

Case 2: Empty string in array
Input: ["flower", "", "flight"]
Output: ""
Reason: No non-empty prefix of empty string

Case 3: No common prefix
Input: ["dog", "racecar", "car"]
Output: ""
Reason: Different first characters

Case 4: One string is complete prefix
Input: ["flow", "flower", "flowing"]
Output: "flow"
Reason: "flow" is entirely contained in others

Case 5: All identical
Input: ["test", "test", "test"]
Output: "test"
Reason: Entire string matches all

Case 6: Different lengths
Input: ["abc", "a", "abcdef"]
Output: "a"
Reason: Limited by shortest string

---

Common Mistakes

Mistake 1: Not handling empty strings
❌ Wrong: Assume all strings non-empty
✓ Right: Check if any string empty OR check bounds

Mistake 2: Using wrong stopping condition
❌ Wrong: Check only character mismatch
✓ Right: Check BOTH out-of-bounds AND mismatch

Mistake 3: Forgetting to return on empty prefix
❌ Wrong: Continue loop when prefix becomes ""
✓ Right: Return immediately when prefix.isEmpty()

Mistake 4: Off-by-one in substring
❌ Wrong: substring(0, i+1) when i is mismatch position
✓ Right: substring(0, i) excludes the mismatch position

---

🎯 Key Takeaways

⚡ Algorithm Progression

Approach 1: Vertical Scanning (Position-by-Position)
  - Check each position across all strings
  - Stop on first mismatch or out-of-bounds

Approach 2: Horizontal Scanning (String-by-String)  
  - Start with first string, reduce until fits all
  - Use indexOf for efficient "starts with" check

Both: O(S) time, O(1) space

🔑 Pattern Recognition

Problem Type: String Prefix Matching
Core Pattern: Scan and stop on disagreement

When to Apply:
✓ Finding common start/end across multiple strings
✓ Need to match beginning of all strings
✓ Can stop early when mismatch found
✓ Shortest string limits search space

Related Problems:
- String Matching in an Array
- Longest Word in Dictionary  
- Implement Trie (for prefix tree)

🧠 Interview Communication

Step 1: "I can scan vertically by position or horizontally by string"
Step 2: "Vertical: check each position across all strings"
Step 3: "Horizontal: reduce first string until it fits all"
Step 4: "Both are O(S) time with O(1) space"
Step 5: "I'll use horizontal scanning for cleaner code"

---

Final Optimal Code (Recall Friendly)

public String longestCommonPrefix(String[] strs) {
    if (strs.length == 0) return "";

    // lets say we assumed the result which is strs[0]
    // if this is not fitting, reduce a character and try and keep on going
    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;
}

Memory Hook: "Start optimistic, reduce until fits all!"

---

Related Patterns

• String Matching in an Array
• Longest Word in Dictionary
• Implement Trie (Prefix Tree)

---

Happy practicing! 🎯