Longest Word in Dictionary
Last Updated: April 4, 2026
Understanding the Problem
We have a list of words and need to find the longest one that has a complete "chain" of prefixes in the dictionary. For a word like "world" to be valid, the dictionary must also contain "w", "wo", "wor", and "worl". Each prefix builds on the previous one by adding exactly one character at the end.
If two valid words have the same length, we pick the lexicographically smaller one. So between "apply" and "apple", we return "apple" because it comes first alphabetically.
The key observation is that this is fundamentally a prefix-chain problem. A word of length k is buildable only if its prefix of length k-1 is also buildable. Words of length 1 are always buildable (they are trivially built from the empty string by adding one character). This recursive structure suggests we can either use sorting with a hash set or a Trie data structure.
Key Constraints:
words.length <= 1000→ The total number of words is small. Even O(n^2) approaches are feasible here.words[i].length <= 30→ Individual words are short. Operations on a single word (like extracting prefixes) are cheap.- Lowercase English letters only → Trie nodes need at most 26 children.
Approach 1: Brute Force (Check All Prefixes)
Intuition
The most direct approach is to take each word, extract every prefix of that word, and check if all those prefixes exist in the dictionary. If they do, the word is "buildable." We keep track of the longest buildable word seen so far, breaking ties by lexicographic order.
To make prefix lookups fast, we toss all words into a hash set first. Then for each word, we check each of its prefixes against the set.
Algorithm
- Insert all words into a hash set for O(1) lookups
- Initialize the result as an empty string
- For each word in the array:
a. Check if every prefix of this word (from length 1 up to length - 1) exists in the hash set
b. If all prefixes exist, compare this word against the current result: update if it is longer, or if it is the same length but lexicographically smaller
- Return the result
Example Walkthrough
Input:
For the word "world", we check prefixes: "w" (in set), "wo" (in set), "wor" (in set), "worl" (in set). All present, so "world" is buildable.
Output:
Code
- Time Complexity: O(n * L^2). We iterate through all n words. For each word of length L, we check up to L-1 prefixes, each costing O(L) for substring extraction.
- Space Complexity: O(n * L). The hash set stores all n words, each up to length L.
The brute force checks every prefix redundantly. What if we processed words from shortest to longest, so we only need to check the immediate prefix?
Approach 2: Sorting + HashSet
Intuition
If we sort the words first by length (shorter words first), then alphabetically within the same length, we can process words in order. By the time we encounter a word of length k, all words of length k-1 have already been processed.
A word is buildable if its prefix of length k-1 (the word minus its last character) is already in our set of buildable words. Words of length 1 are always buildable since they are built from the empty string by adding one character.
By sorting words from shortest to longest and alphabetically within the same length, we guarantee two things. First, when we check a word, its one-character-shorter prefix has already been considered. If that prefix was buildable, it is already in our set. Second, for words of the same length, the lexicographically smallest one comes first. So the first buildable word we find at any given length is automatically the best one at that length.
The beauty of only checking the immediate prefix is that buildability is transitive. If "app" is in the buildable set, it means "ap" was buildable, which means "a" was buildable. We do not need to re-verify the entire chain every time.
Algorithm
- Sort the words by length first, then lexicographically
- Create a hash set of buildable words, initialized with an empty string ""
- Initialize the result as an empty string
- For each word in sorted order:
a. Check if the prefix of length (word.length - 1) is in the buildable set
b. If yes, add this word to the buildable set
c. Update the result if this word is longer than the current result
- Return the result
Example Walkthrough
Code
- Time Complexity: O(n L log n). Sorting takes O(n L log n) where L is the max word length. The single pass through the sorted array takes O(n * L) for substring operations. Sorting dominates.
- Space Complexity: O(n * L). The hash set stores up to n words, each of length up to L.
The sorting approach is clean, but a Trie naturally represents shared prefixes without substring creation. Can we walk the Trie directly?
Approach 3: Trie with DFS
Intuition
A Trie (prefix tree) is a natural fit here because the problem is fundamentally about prefixes. We insert all words into a Trie, marking which nodes represent the end of a word. Then we search for the longest path from the root where every node along the way is a complete word.
Each node in the Trie represents a prefix. If that prefix is itself a word in the dictionary (its isEnd flag is true), then we can "build" up to that point. We want the deepest node reachable by following only edges where each intermediate node is a complete word. A DFS starting from the root, exploring children alphabetically and only visiting end-of-word nodes, does exactly this.
Algorithm
- Build a Trie by inserting all words
- Run DFS from the root of the Trie
- At each node, only visit children that are marked as the end of some word
- Track the deepest valid path encountered during DFS
- If two paths have the same depth, prefer the lexicographically smaller one (handled by exploring children a-z)
- Return the word corresponding to the deepest valid path
Example Walkthrough
Code
- Time Complexity: O(n L). Building the Trie takes O(n L) where n is the number of words and L is the max word length. The DFS visits each node at most once.
- Space Complexity: O(n L). The Trie stores up to n L nodes, each with an array of 26 children pointers.