← ~/lc-grind/posts

#14 - Longest Common Prefix

September 24, 2025

Longest Common Prefix

Problem Description

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: ""
Explanation: There is no common prefix among the input strings.

Constraints:

  • 1 <= strs.length <= 200
  • 0 <= strs[i].length <= 200
  • strs[i] consists of only lowercase English letters if it is non-empty.

Solution

1. Problem Deconstruction

Technical Restatement: Given an array of strings strs, determine the maximum-length contiguous character sequence that appears at the beginning of every string in the array. Formally, find the longest string P such that for every string S in strs, S starts with P. If no such non-empty prefix exists, return the empty string.

Beginner-Friendly Version: We have a list of words. We want to find the longest starting part that all words share. For example, in [“flower”,“flow”,“flight”], all words start with “fl”. If the words don’t share any starting letters (like [“dog”,“racecar”,“car”]), we return an empty string.

Mathematical Formulation: Let strs = [s₁, s₂, ..., sₙ] where each sᵢ is a string of length lᵢ. We seek the maximum integer k such that for every pair of strings (sᵢ, sⱼ) in strs, and for every index m (0 ≤ m < k), the character at position m is identical: sᵢ[m] = sⱼ[m]. The solution is the substring s₀[0:k] (or any sᵢ[0:k]).

Constraint Analysis:

  • 1 <= strs.length <= 200: The input array is non-empty but reasonably small. Even O(n²) solutions (200² = 40,000 operations) are feasible.
  • 0 <= strs[i].length <= 200: Individual strings can be empty. This is a critical edge case (e.g., ["", "abc"] → immediately return “”).
  • Strings contain only lowercase English letters: No special character handling needed. Character comparisons are straightforward.

Hidden Edge Cases:

  • Single string array: ["abc"] → the entire string is the common prefix.
  • Empty string in array: ["", "abc"] → immediately return “”.
  • All strings empty: ["", "", ""] → common prefix is “”.
  • Very short strings: ["a", "ab", "abc"] → stop at min length.
  • No common prefix: ["abc", "def", "ghi"] → return “”.

2. Intuition Scaffolding

Real-World Metaphor (Dictionary Index): Imagine looking up words in a dictionary’s index where words are grouped by their starting letters. The common prefix is like the shared section where your finger would rest before the words diverge into different alphabetical branches.

Gaming Analogy (Tower Defense Pathfinding): In tower defense games, enemies follow a shared path until they reach branching points. The common prefix is the initial segment where all enemy units travel together before taking different routes.

Math Analogy (Set Intersection): The common prefix is the intersection of all strings when viewed as sequences, but with the constraint that we only consider characters in order from the beginning. It’s like finding the longest initial segment in the Cartesian product of the strings.

Common Pitfalls:

  1. Assuming non-empty arrays: While constraints guarantee at least one string, code should handle empty array if input validation is required.
  2. Comparing beyond shortest string: Without checking minimum length, you’ll get index errors.
  3. Overlooking empty strings: An empty string in the array makes the common prefix immediately empty.
  4. Continuing after mismatch: Some approaches might not break early when a mismatch is found.
  5. Unnecessary complexity: With small constraints, even suboptimal solutions work, but interviewers expect efficiency.

3. Approach Encyclopedia

Approach 1: Horizontal Scanning

  • What: Compare the first string with the second to find their common prefix, then compare that result with the third, and so on.
  • Why: Intuitive, reduces the problem step by step.
  • How:
prefix = strs[0]
for each next string in strs[1:]:
    while next_string doesn't start with prefix:
        shorten prefix by one character
        if prefix becomes empty: return ""
return prefix
  • Complexity:
    • Time: O(S) where S is the sum of all characters. Worst-case when all strings are identical (O(n*m)).
    • Space: O(1) extra space.
  • Visualization:
Initial: prefix = "flower"
Compare "flower" and "flow" → prefix = "flow"
Compare "flow" and "flight" → prefix = "fl"
Result: "fl"

Approach 2: Vertical Scanning

  • What: Compare characters at the same index across all strings before moving to the next index.
  • Why: More efficient when strings have different lengths or early mismatches.
  • How:
for each character index from 0 to min_length-1:
    current_char = strs[0][index]
    for each string in strs[1:]:
        if string[index] != current_char: 
            return strs[0][0:index]
return strs[0][0:min_length]
  • Complexity:
    • Time: O(n*m) worst-case, but stops at first mismatch.
    • Space: O(1).
  • Visualization:
Index 0: 'f' in all strings → continue
Index 1: 'l' in all strings → continue
Index 2: 'o' vs 'i' → mismatch → return "fl"

Approach 3: Divide and Conquer

  • What: Split the array into halves, find LCP for each half, then combine results.
  • Why: Demonstrates recursive thinking (though overkill for this problem).
  • How:
function LCP(strs, left, right):
    if left == right: return strs[left]
    mid = (left + right) // 2
    lcp_left = LCP(strs, left, mid)
    lcp_right = LCP(strs, mid+1, right)
    return common_prefix(lcp_left, lcp_right)
  • Complexity:
    • Time: O(S) same as horizontal scanning.
    • Space: O(m*log n) for recursion stack.

Approach 4: Binary Search on Prefix Length

  • What: Use binary search to find the maximum length L where all strings share the first L characters.
  • Why: Theoretically optimal for very long strings.
  • How:
min_len = min length among strings
low, high = 0, min_len
while low <= high:
    mid = (low + high) // 2
    if all strings share prefix of length mid:
        low = mid + 1
    else:
        high = mid - 1
return strs[0][0:high]
  • Complexity:
    • Time: O(nmlog m) where m is min length.
    • Space: O(1).

4. Code Deep Dive

Optimal Solution (Vertical Scanning):

def longestCommonPrefix(strs):
    if not strs:  # Handle empty array edge case
        return ""
    
    # Find the minimum length string to avoid index errors
    min_len = min(len(s) for s in strs)
    
    # Vertical scanning: check each character index
    for i in range(min_len):
        current_char = strs[0][i]  # Character to match
        # Check all other strings at this position
        for string in strs[1:]:
            if string[i] != current_char:
                return strs[0][:i]  # Return prefix up to mismatch
    
    return strs[0][:min_len]  # All characters matched

Line-by-Line Analysis:

  1. Line 2-3: Handle empty input array (though constraints say length ≥ 1, good practice)
  2. Line 5-6: Find minimum length to prevent index errors. Critical for ["ab", "a"] → min_len=1
  3. Line 9: current_char from first string establishes the benchmark
  4. Line 11-12: Compare with all other strings. Mismatch immediately returns the prefix
  5. Line 14: If we complete the loop, the entire shortest string is the common prefix

Edge Case Handling:

  • [""]: min_len=0 → returns “” immediately
  • ["a", "b"]: Fails at i=0 → returns “”
  • ["abc", "ab"]: min_len=2 → matches both characters → returns “ab”

5. Complexity War Room

Hardware-Aware Analysis:

  • With n=200 and m=200, worst-case 40,000 character comparisons.
  • At 1 byte per char, ~40KB data fits in L1 cache (typically 64-256KB).
  • Even worst-case performance is negligible on modern hardware.

Approach Comparison Table:

Approach Time Complexity Space Complexity Readability Interview Viability
Horizontal O(S) O(1) 8/10 Good for small inputs
Vertical O(S) O(1) 9/10 ✅ Optimal + Simple
Divide & Conquer O(S) O(m log n) 6/10 Overcomplicated
Binary Search O(nm log m) O(1) 7/10 Good for long strings

6. Pro Mode Extras

Variants & Extensions:

  1. Longest Common Suffix: Reverse strings and apply LCP, then reverse result.
  2. Longest Common Substring: Different problem requiring dynamic programming.
  3. Case-Insensitive LCP: Convert all strings to lowercase first.
  4. LCP with Wildcards: More complex pattern matching problem.

Interview Cheat Sheet:

  • First Mention: “This can be solved in O(S) time where S is total characters, with O(1) extra space”
  • Key Insight: “We can stop comparing as soon as we find any mismatch”
  • Edge Cases: “Remember to handle empty strings and single-string inputs”
  • Optimization: “Vertical scanning tends to be faster in practice due to early termination”

Follow-up Questions:

  • How would you make this algorithm parallelizable? (Divide strings among processors)
  • What if strings are too large for memory? (External merge sort approach)
  • How to handle Unicode characters? (Python handles this transparently)