14. Longest Common Prefix

The Longest Common Prefix (LeetCode 14) is a core string manipulation problem frequently asked in FAANG interviews, including Google, Amazon, Microsoft, Meta, and Apple. While it appears simple, it is used to evaluate a candidate’s ability to write efficient, production-ready code for real-world string processing tasks.

Beyond brute-force solutions, interviewers expect familiarity with scalable approaches such as the Trie (Prefix Tree), which enables efficient prefix queries with O(S) complexity. The problem is also a gateway to string search optimization and dictionary lookup patterns.

Key techniques include horizontal and vertical scanning, binary search on prefix length, and Trie-based implementations, along with a strong understanding of time and space complexity trade-offs.

It prepares you for a broader family of problems, including:

• Autocomplete & Predictive Text: Finding all words starting with a given prefix efficiently
• Spell Checking: Identifying valid or closest matches in a dictionary
• Network Routing (LPM): Longest Prefix Match used in IP forwarding systems

Problem statement

You are given an array of strings called strs. Your task is to find the longest prefix string that is common to every string in the array. If no such prefix exists, return an empty string "".

A prefix of a string is any leading portion of it, including the empty string and the full string itself. The result must be a string that every element of strs starts with, and it should be as long as possible.

Constraints

• 1 ≤ strs.length ≤ 200
• 0 ≤ strs[i].length ≤ 200
• strs[i] consists of only lowercase English letters if it’s non-empty.

Examples

Why brute force prefix matching does not scale for finding longest common prefix

The most straightforward approach is to take the first string as a reference prefix and compare it character by character with every other string. For each position, you scan all strings to check whether they share the same character. While this produces the correct result, it leads to repeated work because each new position rechecks characters that were already validated in previous steps.

Another brute-force variation is to generate all possible prefixes of the first string and verify each one across the entire array. However, this quickly becomes inefficient. With n strings of average length m, the solution can degrade to O(n × m) comparisons in the worst case, with no reuse of intermediate results between checks.

More importantly, these approaches fail to capture shared structure between strings. They do not build any reusable representation of prefix relationships, which becomes a major limitation when dealing with large datasets or repeated prefix queries. This is exactly why optimized techniques like Trie-based prefix processing or structured scanning approaches are preferred in scalable systems.

Optimized approach using trie for LCP

The key idea is that after inserting all strings into the trie, the longest common prefix (LCP) is found by traversing from the root as long as two conditions hold: each node has exactly one child, and no node is marked as the end of a word. The moment a node has multiple children, it indicates a divergence between strings. Similarly, if a node marks the end of a word, it means one string has ended, and the prefix cannot extend further.

By constructing the trie once and then following a single downward path from the root, we can extract the result efficiently in O(S) time, where S is the total number of characters across all strings. This approach is both clean and scalable, especially for systems involving repeated prefix queries or large dictionaries.

Why the optimized approach works well

The trie collapses all prefix comparisons into a single shared structure. Instead of comparing each string against every other string, you insert each string once, and the trie records exactly where paths overlap and where they split. The traversal to find the common prefix is then a simple linear walk from the root, stopping at the first point of divergence.

This approach avoids revisiting characters, handles the empty string edge case naturally (an empty string contributes no children to the root, so the walk ends immediately), and provides a clean separation between data construction (insertion) and query (traversal). It also generalizes beautifully: the same trie can answer autocomplete queries, count words with a given prefix, or find the shortest unique prefix for each string.

Step-by-step algorithm

1. If the input array strs is empty, return an empty string immediately.
2. Create a new trie and insert every string from strs into it, character by character, marking the final character of each string as an end-of-word node.
3. Start traversal from the root node and initialize an empty string prefix.
4. At the current node, check two conditions: the node must not be marked as the end of a word, and it must have exactly one child.
5. If both conditions hold, retrieve the single child character, append it to the prefix string, and move to that child node.
6. Repeat step 4 until either condition is violated (multiple children or end-of-word node).
7. Return the accumulated prefix string as the longest common prefix.

1 / 12

Python implementation

class TrieNode:
    def __init__(self):
        # Each node stores a dictionary of children and a word-end flag
        self.children = {}
        self.is_end_of_word = False


class Trie:
    def __init__(self):
        # The root node is an empty node that anchors the trie
        self.root = TrieNode()

    def insert(self, word):
        # Walk through each character and create nodes as needed
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        # Mark the last node as the end of this word
        node.is_end_of_word = True

    def get_root(self):
        return self.root


def find_longest_common_prefix(trie):
    # Start at the root and collect characters along the single-child path
    prefix = ""
    node = trie.get_root()

    while node and not node.is_end_of_word and len(node.children) == 1:
        # Only one child means all inserted strings share this character
        char, next_node = list(node.children.items())[0]
        prefix += char
        node = next_node

    return prefix


def longest_common_prefix(strs):
    # Handle empty input immediately
    if not strs:
        return ""

    # Build the trie from all strings
    trie = Trie()
    for word in strs:
        trie.insert(word)

    # Traverse the trie to extract the longest common prefix
    return find_longest_common_prefix(trie)


def main():
    test_cases = [
        ["apple", "app", "application", "applet", "appreciate"],
        ["hello"],
        ["abc", "def", "ghi"],
        ["interview", "inter", "internal", "interactive"],
        ["", "empty", "example"],
    ]

    expected_outputs = [
        "app",
        "hello",
        "",
        "inter",
        "",
    ]

    for i, strs in enumerate(test_cases):
        result = longest_common_prefix(strs)
        status = "PASS" if result == expected_outputs[i] else "FAIL"
        print(f"{i + 1}.\tInput: {strs}")
        print(f"\tLongest common prefix: \"{result}\"")
        print("-" * 80)


if __name__ == "__main__":
    main()

Time complexity

The time complexity is O(n x m), where n is the number of strings in strs and m is the average length of the strings. Inserting all strings into the trie requires visiting every character across all strings, which totals O(n x m) operations. The subsequent traversal to find the longest common prefix walks at most m nodes (the length of the shortest string), which is dominated by the insertion cost. Overall, the algorithm runs in linear time relative to the total number of characters in the input.

Space complexity

The space complexity is O(S), where S is the total number of characters across all strings in the input array. In the worst case, when no strings share any prefix, every character creates a new trie node, consuming space proportional to the sum of all string lengths. In practice, shared prefixes reduce the actual number of nodes. The prefix string built during traversal uses at most O(m) additional space, where m is the length of the shortest string, but this is dominated by the trie storage.

Edge cases

• Empty string in the array: If any string in strs is "", the trie root gains no children from that insertion, but that string marks the root as an end-of-word node. The traversal stops immediately, correctly returning "".
• Single string in the array: With only one string, every character forms a single-child path in the trie. The traversal collects the entire string, returning it as the prefix.
• All strings are identical: The trie has a single path with no branching. The traversal continues until it hits the end-of-word marker, returning the full string.
• No shared first character: The root node immediately has multiple children, so the traversal returns "" without collecting any characters.

Common pitfalls

• Forgetting to mark end-of-word nodes: Without the is_end_of_word flag, the traversal might extend the prefix beyond the length of a shorter string. For example, with ["app", "apple"], failing to stop at the end of "app" would incorrectly return "apple".
• Not handling empty strings in the input: An empty string means the common prefix must be empty. If your insertion logic skips empty strings instead of still marking the root, the traversal can produce wrong results.
• Using string concatenation in a loop: In Python, building the prefix with += inside a loop creates a new string each time. For very long prefixes this becomes O(m^2). Using a list and joining at the end is more efficient, though for the given constraints it does not cause issues.
• Assuming the array is non-empty: The problem guarantees at least one string, but defensive code should still handle an empty array to avoid index errors during interviews.