Problem Description

You are given an array of strings words representing an English Dictionary. Your task is to find the longest word in this dictionary that can be built one character at a time by other words in the dictionary.

The key requirement is that the word must be buildable incrementally from left to right. This means:

• To build a word of length n, all its prefixes of lengths 1, 2, 3, ..., n-1 must also exist in the dictionary
• Each step adds exactly one character to the end of an existing word

For example, if words = ["a", "ap", "app", "apple"], then "apple" can be built because:

• "a" exists in the dictionary
• "ap" exists (built by adding 'p' to "a")
• "app" exists (built by adding 'p' to "ap")
• "apple" exists (built by adding 'l' and 'e' to "app")

If multiple words have the same maximum length, return the one that comes first lexicographically (alphabetically). If no word can be built this way, return an empty string.

The solution uses a Trie data structure to efficiently store and search for words. The Trie's search method is modified to check that every prefix of a word (not just the complete word) exists as a complete word in the dictionary by verifying the is_end flag at each character. This ensures the word can be built incrementally as required.

Intuition

The core insight is recognizing that we need to verify if every prefix of a word exists as a complete word in the dictionary. When we think about checking prefixes efficiently, a Trie naturally comes to mind because it stores words in a prefix-tree structure where common prefixes are shared.

Consider how we would check if a word like "apple" can be built incrementally:

• We need to verify "a" is a complete word
• Then verify "ap" is a complete word
• Then verify "app" is a complete word
• Then verify "appl" is a complete word
• Finally verify "apple" is a complete word

A naive approach would require searching the entire word list for each prefix, resulting in inefficient repeated searches. However, with a Trie, we can traverse character by character and check at each node whether it marks the end of a valid word using the is_end flag.

The key modification to the standard Trie search is that instead of just checking if the final node has is_end = True, we need to verify that EVERY intermediate node along the path also has is_end = True. This ensures all prefixes are valid words.

Once we have this efficient way to verify if a word can be built incrementally, we simply iterate through all words, check each one, and keep track of the longest valid word. When we encounter words of equal length, we update our answer only if the new word is lexicographically smaller (using the string comparison ans > w).

The Trie structure makes this solution efficient because we only build the Trie once with O(total characters) time, and then each word verification takes O(word length) time by walking down the Trie path once.

Learn more about Trie and Sorting patterns.

Solution Approach

The solution uses a Trie (prefix tree) data structure to efficiently store and search for words. Let's walk through the implementation step by step:

Trie Implementation

First, we define a [Trie](/problems/trie_intro) class with the following components:

1. Node Structure: Each Trie node contains:

   • children: An array of 26 elements (for letters 'a' to 'z'), where children[i] points to the child node for character chr(ord('a') + i)
   • is_end: A boolean flag indicating if this node marks the end of a valid word

2. Insert Method:

   def insert(self, w: str):
       node = self
       for c in w:
           idx = ord(c) - ord("a")  # Convert character to index (0-25)
           if node.children[idx] is None:
               node.children[idx] = [Trie](/problems/trie_intro)()  # Create new node if needed
           node = node.children[idx]
       node.is_end = True  # Mark the end of the word

3. Modified Search Method:

   def search(self, w: str) -> bool:
       node = self
       for c in w:
           idx = ord(c) - ord("a")
           if node.children[idx] is None:
               return False  # Character path doesn't exist
           node = node.children[idx]
           if not node.is_end:
               return False  # Prefix is not a complete word
       return True

   The crucial modification here is checking node.is_end at each step, ensuring every prefix is a complete word in the dictionary.

Main Solution Logic

1. Build the Trie: Insert all words from the input array into the Trie

   trie = Trie()
   for w in words:
       trie.insert(w)

2. Find the Longest Valid Word: Iterate through all words and check if each can be built incrementally

   ans = ""
   for w in words:
       if [trie](/problems/trie_intro).search(w):  # Check if word can be built incrementally
           if len(ans) < len(w) or (len(ans) == len(w) and ans > w):
               ans = w

   The update condition ensures we keep:

   • The longest word when lengths differ (len(ans) < len(w))
   • The lexicographically smallest word when lengths are equal (len(ans) == len(w) and ans > w)

Time and Space Complexity

• Time Complexity: O(n × m) where n is the number of words and m is the average length of words

  • Building the Trie: O(n × m)
  • Searching all words: O(n × m)

• Space Complexity: O(ALPHABET_SIZE × n × m) for storing the Trie structure, where ALPHABET_SIZE = 26

This approach efficiently solves the problem by leveraging the Trie's ability to share common prefixes and quickly verify if all prefixes of a word exist as complete words in the dictionary.

Example Walkthrough

Let's walk through a concrete example with words = ["w", "wo", "wor", "worl", "world", "a", "ap", "app"].

Step 1: Build the Trie

We insert each word into the Trie. After insertion, the Trie structure looks like this (showing only relevant paths):

        root
       /    \
      w      a
     /        \
    o(end)    p(end)
   /           \
  r(end)       p(end)
 /
l(end)
 \
  d(end)

Each node marked with (end) has is_end = True, indicating a complete word ends there.

Step 2: Check Each Word

Now we iterate through each word and use our modified search method:

1. "w":

   • Check 'w': Node exists but is_end = False → Return False
   • Cannot be built incrementally (no single letter "w" in dictionary)

2. "wo":

   • Check 'w': Node exists but is_end = False → Return False
   • Cannot be built (needs "w" to exist first)

3. "wor":

   • Check 'w': Node exists but is_end = False → Return False
   • Cannot be built

4. "worl":

   • Check 'w': Node exists but is_end = False → Return False
   • Cannot be built

5. "world":

   • Check 'w': Node exists but is_end = False → Return False
   • Cannot be built

6. "a":

   • Check 'a': Node exists and is_end = True → Continue
   • Reached end of word → Return True
   • Valid! Update ans = "a"

7. "ap":

   • Check 'a': Node exists and is_end = True → Continue
   • Check 'p': Node exists and is_end = True → Continue
   • Reached end of word → Return True
   • Valid! Since len("ap") > len("a"), update ans = "ap"

8. "app":

   • Check 'a': Node exists and is_end = True → Continue
   • Check 'p': Node exists and is_end = True → Continue
   • Check 'p': Node exists and is_end = True → Continue
   • Reached end of word → Return True
   • Valid! Since len("app") > len("ap"), update ans = "app"

Final Result: "app" is the longest word that can be built incrementally.

The key insight is that "world" cannot be built even though it's the longest word, because its prefixes "w", "wo", "wor", and "worl" don't all exist as complete words in the dictionary. In contrast, "app" can be built because:

• "a" exists as a complete word
• "ap" exists and can be built by adding 'p' to "a"
• "app" exists and can be built by adding 'p' to "ap"

Solution Implementation

Time and Space Complexity

Time Complexity: O(L)

The algorithm consists of two main phases:

1. Building the Trie: We iterate through all words and insert each one into the Trie. For each word, we traverse through its characters. Since we process every character of every word exactly once during insertion, this takes O(L) time, where L is the sum of lengths of all words.

2. Searching in the Trie: We iterate through all words again and search each one. The search method traverses each character of the word and checks if all prefixes exist as complete words (using the is_end flag). In the worst case, we examine every character of every word once, which is also O(L).

Therefore, the total time complexity is O(L) + O(L) = O(L).

Space Complexity: O(L)

The space is dominated by the Trie structure. In the worst case, when there are no common prefixes among words, each character of each word creates a new node in the Trie. Each node contains:

• An array of 26 pointers (for lowercase letters a-z)
• A boolean flag is_end

However, the number of nodes created is bounded by the total number of characters across all words. Even though each node has an array of size 26, the total number of nodes cannot exceed L (one node per character in the worst case). Therefore, the space complexity is O(L).

The additional space used for the ans variable and temporary variables during traversal is O(max word length), which is bounded by O(L), so it doesn't affect the overall space complexity.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Prefix Validation Logic

The Pitfall: A common mistake is implementing the search method to only check if the final word exists in the trie, without verifying that every prefix is also a complete word. This would look like:

def search(self, word: str) -> bool:
    current_node = self
    for char in word:
        index = ord(char) - ord('a')
        if current_node.children[index] is None:
            return False
        current_node = current_node.children[index]
    return current_node.is_end  # Only checks if the final word exists

This implementation would incorrectly accept words like "apple" even if "ap" or "app" don't exist as complete words in the dictionary.

The Solution: Check is_end flag at every character position (except the starting empty prefix):

def search(self, word: str) -> bool:
    current_node = self
    for i, char in enumerate(word):
        index = ord(char) - ord('a')
        if current_node.children[index] is None:
            return False
        current_node = current_node.children[index]
        # For non-empty prefixes, verify they're complete words
        if not current_node.is_end:
            return False
    return True

2. Handling Single-Character Words Incorrectly

The Pitfall: Some implementations might skip checking single-character words or handle them as a special case, assuming they can always be built. However, a single-character word like "a" must actually exist in the dictionary to be valid.

The Solution: The search method should work uniformly for all word lengths. Single-character words will naturally be validated by checking if they exist in the trie with is_end = True.

3. Wrong Lexicographical Comparison

The Pitfall: When comparing words of the same length, using the wrong comparison operator:

# Incorrect - keeps lexicographically larger word
if len(longest_word) == len(word) and longest_word < word:
    longest_word = word

The Solution: Use the correct comparison to keep the lexicographically smaller word:

# Correct - keeps lexicographically smaller word
if len(longest_word) == len(word) and longest_word > word:
    longest_word = word

4. Not Handling Empty Input

The Pitfall: The code might fail when given an empty array or when no valid buildable word exists.

The Solution: Initialize the answer as an empty string, which naturally handles both cases:

• Empty input array → returns empty string
• No buildable words → returns empty string

5. Assuming Words Are Already Sorted

The Pitfall: Some might try to optimize by assuming the input is sorted by length or lexicographically, leading to early termination or incorrect results.

The Solution: Always check all words in the input array without making assumptions about their order. The current implementation correctly iterates through all words regardless of their order.