Longest Common Prefix

Vertical scanning and divide-and-conquer approaches

Finding the longest common prefix among an array of strings is a classic problem that tests your understanding of string comparison techniques and algorithm design patterns.

---

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

This is LeetCode Problem #14 - an Easy difficulty problem.

Examples

Input	Output	Explanation
["flower","flow","flight"]	"fl"	Common prefix is "fl"
["dog","racecar","car"]	""	No common prefix
["interspecies","interstellar","interstate"]	"inters"	All start with "inters"
["a"]	"a"	Single string is its own prefix
[]	""	Empty array has no prefix

Constraints

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

---

Approach 1: Vertical Scanning

Compare characters column by column across all strings.

How It Works

1. Take the first string as reference
2. For each character position (column):
   • Check if all strings have this character at this position
   • If any string is shorter or has a different character, stop
3. Return the prefix found

Mermaid Diagram

Visual Walkthrough

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

Position 0:  f  f  f  -> All match 'f' -> prefix = "f"
Position 1:  l  l  l  -> All match 'l' -> prefix = "fl"
Position 2:  o  o  i  -> Mismatch! 'o' != 'i'

Return "fl"

Solution

Python

def longestCommonPrefix(strs: list[str]) -> str:
    """
    Find longest common prefix using vertical scanning.

    Args:
        strs: List of strings to compare

    Returns:
        Longest common prefix string

    Time: O(S) where S = sum of all characters in all strings
    Space: O(1) - only using a few variables
    """
    if not strs:
        return ""

    # Use first string as reference
    for i in range(len(strs[0])):
        char = strs[0][i]

        # Check this position in all other strings
        for j in range(1, len(strs)):
            # If string is shorter or character doesn't match
            if i >= len(strs[j]) or strs[j][i] != char:
                return strs[0][:i]

    return strs[0]

Java

public String longestCommonPrefix(String[] strs) {
    if (strs == null || strs.length == 0) return "";
    for (int i = 0; i < strs[0].length(); i++) {
        char c = strs[0].charAt(i);
        for (int j = 1; j < strs.length; j++) {
            if (i >= strs[j].length() || strs[j].charAt(i) != c) {
                return strs[0].substring(0, i);
            }
        }
    }
    return strs[0];
}

Complexity: Time O(S) · Space O(1)

• Time: O(S) where S is the sum of all characters in all strings - in worst case we compare every character when all strings are identical
• Space: O(1) - only using a few pointer variables, no additional data structures

---

Approach 2: Horizontal Scanning

Compare strings pairwise, reducing the prefix each time.

How It Works

1. Start with the first string as the prefix
2. Compare with each subsequent string
3. Reduce prefix until it matches the beginning of each string

def longestCommonPrefix_horizontal(strs: list[str]) -> str:
    """
    Find LCP using horizontal scanning (pairwise comparison).

    Time: O(S) where S = sum of all characters
    Space: O(1)
    """
    if not strs:
        return ""

    prefix = strs[0]

    for i in range(1, len(strs)):
        # Reduce prefix until it matches start of current string
        while not strs[i].startswith(prefix):
            prefix = prefix[:-1]
            if not prefix:
                return ""

    return prefix

Complexity: Time O(S) · Space O(1)

• Time: O(S) where S is the sum of all characters - prefix shrinks character by character until it matches each string
• Space: O(1) - only storing the prefix string which shrinks from the first string

Visual Walkthrough

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

Start: prefix = "flower"

Compare with "flow":
  "flow".startswith("flower")? No
  prefix = "flowe"
  "flow".startswith("flowe")? No
  prefix = "flow"
  "flow".startswith("flow")? Yes!

Compare with "flight":
  "flight".startswith("flow")? No
  prefix = "flo"
  "flight".startswith("flo")? No
  prefix = "fl"
  "flight".startswith("fl")? Yes!

Return "fl"

---

Approach 3: Divide and Conquer

Recursively split the array and find LCP of each half.

def longestCommonPrefix_divideConquer(strs: list[str]) -> str:
    """
    Find LCP using divide and conquer.

    Time: O(S) where S = sum of all characters
    Space: O(m * log n) where m = length of shortest string
           (for recursion stack and intermediate strings)
    """
    if not strs:
        return ""

    def commonPrefix(left: str, right: str) -> str:
        """Find common prefix of two strings."""
        min_len = min(len(left), len(right))
        for i in range(min_len):
            if left[i] != right[i]:
                return left[:i]
        return left[:min_len]

    def divideAndConquer(left: int, right: int) -> str:
        if left == right:
            return strs[left]

        mid = (left + right) // 2
        lcp_left = divideAndConquer(left, mid)
        lcp_right = divideAndConquer(mid + 1, right)

        return commonPrefix(lcp_left, lcp_right)

    return divideAndConquer(0, len(strs) - 1)

Complexity: Time O(S) · Space O(m log n)

• Time: O(S) where S is the sum of all characters - each character is compared once during the merge process
• Space: O(m * log n) where m is the shortest string length - recursion stack depth is log n, each level stores intermediate prefix strings

---

Approach 4: Binary Search

Use binary search on the length of the prefix.

def longestCommonPrefix_binarySearch(strs: list[str]) -> str:
    """
    Find LCP using binary search on prefix length.

    Time: O(S * log m) where m = length of shortest string
    Space: O(1)
    """
    if not strs:
        return ""

    def isCommonPrefix(length: int) -> bool:
        """Check if prefix of given length is common to all strings."""
        prefix = strs[0][:length]
        return all(s.startswith(prefix) for s in strs)

    # Binary search on the length
    min_len = min(len(s) for s in strs)
    low, high = 0, min_len

    while low < high:
        mid = (low + high + 1) // 2  # Upper middle
        if isCommonPrefix(mid):
            low = mid
        else:
            high = mid - 1

    return strs[0][:low]

Complexity: Time O(S log m) · Space O(1)

• Time: O(S * log m) where m is the shortest string length - binary search on length with O(S) verification at each step
• Space: O(1) - only storing indices for binary search boundaries

---

Approach 5: Using Python's Built-in (Pythonic)

import os

def longestCommonPrefix_pythonic(strs: list[str]) -> str:
    """
    Pythonic solution using os.path.commonprefix.

    Note: This works but may not be accepted in interviews
    as it uses a library function.
    """
    return os.path.commonprefix(strs)


def longestCommonPrefix_zip(strs: list[str]) -> str:
    """
    Using zip to compare characters column-wise.

    Time: O(S)
    Space: O(m) for the zip objects
    """
    if not strs:
        return ""

    prefix = []
    for chars in zip(*strs):
        if len(set(chars)) == 1:  # All same
            prefix.append(chars[0])
        else:
            break

    return ''.join(prefix)

Complexity: Time O(S) · Space O(m)

• Time: O(S) where S is the sum of all characters - zip iterates through all strings column by column
• Space: O(m) where m is the shortest string length - for the zip iterator objects and result prefix list

---

Approach 6: Sort and Compare

After sorting, compare only the first and last strings.

def longestCommonPrefix_sort(strs: list[str]) -> str:
    """
    Sort strings, then compare first and last only.

    Key insight: After lexicographic sorting, the common prefix
    of all strings must be the common prefix of first and last.

    Time: O(n log n * m) for sorting, O(m) for comparison
    Space: O(n) for sorted copy or O(1) if in-place
    """
    if not strs:
        return ""

    strs.sort()
    first, last = strs[0], strs[-1]

    i = 0
    while i < len(first) and i < len(last) and first[i] == last[i]:
        i += 1

    return first[:i]

Complexity: Time O(n log n * m + m) · Space O(n)

• Time: O(n log n * m) for sorting n strings of average length m, plus O(m) for final comparison
• Space: O(n) for the sorted array copy, or O(1) if sorting in-place (but modifies input)

---

Complexity Comparison

Approach	Time	Space	Best For
Vertical Scanning	O(S)	O(1)	General use
Horizontal Scanning	O(S)	O(1)	Simple implementation
Divide & Conquer	O(S)	O(m log n)	Parallel processing
Binary Search	O(S log m)	O(1)	Very long strings
Sort + Compare	O(n log n * m)	O(n)	Already sorted input
Zip (Pythonic)	O(S)	O(m)	Quick coding

Where:

• S = sum of all character counts
• n = number of strings
• m = length of shortest string

---

Edge Cases

Case	Input	Output	Handling
Empty array	[]	""	Return empty
Single string	["abc"]	"abc"	Return the string
Empty string in array	["", "abc"]	""	LCP is empty
No common prefix	["dog", "cat"]	""	First chars differ
All identical	["abc", "abc"]	"abc"	Return full string

---

Interview Tips

1. Start with vertical scanning: Most intuitive and efficient
2. Ask about input size: Binary search for very long strings
3. Handle edge cases first: Empty array, single string
4. Mention optimization: Early termination when prefix becomes empty

Common Follow-up Questions

• "What if strings are very long?" - Binary search on length
• "What if we have many strings?" - Divide and conquer for parallelization
• "What if strings change frequently?" - Use a Trie data structure

---

Trie-Based Solution (Advanced)

For multiple queries or dynamic updates, a Trie is optimal:

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end = True

    def longestCommonPrefix(self) -> str:
        """
        Find LCP by traversing until a branch point.
        """
        prefix = []
        node = self.root

        while node and len(node.children) == 1 and not node.is_end:
            char = next(iter(node.children))
            prefix.append(char)
            node = node.children[char]

        return ''.join(prefix)


def longestCommonPrefix_trie(strs: list[str]) -> str:
    """
    Find LCP using a Trie.

    Time: O(S) to build trie, O(m) to find LCP
    Space: O(S) for trie

    Best for: Multiple queries after initial build
    """
    if not strs:
        return ""

    trie = Trie()
    for s in strs:
        if not s:  # Empty string means no common prefix
            return ""
        trie.insert(s)

    return trie.longestCommonPrefix()

Complexity: Time O(S) · Space O(S)

• Time: O(S) to build the trie where S is the sum of all characters, plus O(m) to find the LCP
• Space: O(S) to store all characters in the trie nodes - each character creates a new node

---

Related Problems

Implement Trie - Prefix Tree (LeetCode 208)

Problem: Implement a trie with insert, search, and startsWith methods.

Key Insight: Trie nodes contain children map and end-of-word flag. Each path from root represents a prefix.

Approach: Insert by creating nodes for each character. Search follows path and checks end flag. startsWith only checks path existence.

Complexity: O(m) for all operations where m is key length, O(alphabet_size * n * m) space

Search Suggestions System (LeetCode 1268)

Problem: Given products array and searchWord, return list of suggested products after each character of searchWord is typed. Suggest at most 3 products with common prefix, sorted lexicographically.

Key Insight: Can use Trie for prefix matching or binary search on sorted array.

Approach: Sort products. For each prefix, binary search for leftmost match, take up to 3 products starting there.

Complexity: O(n log n + m * n) time for sorting + queries, or O(sum of lengths) for Trie

Longest Common Subsequence (LeetCode 1143)

Problem: Given two strings, return the length of their longest common subsequence (not necessarily contiguous).

Key Insight: Classic 2D DP. Different from prefix - subsequence can skip characters.

Approach: dp[i][j] = LCS length for first i chars of text1 and first j chars of text2. Match adds 1, mismatch takes max of excluding either.

Complexity: O(m * n) time, O(m * n) space (can optimize to O(n))

---

Summary

Key Point	Details
Best Approach	Vertical scanning for simplicity
Time Complexity	O(S) for most approaches
Space Complexity	O(1) for vertical/horizontal scanning
Key Insight	Only need to check until first mismatch

Takeaway: The vertical scanning approach is the most intuitive and efficient for typical inputs. For specialized cases (very long strings, multiple queries), consider binary search or Trie-based solutions.

---

References

• LeetCode - Longest Common Prefix
• GeeksforGeeks - Longest Common Prefix