Longest Word in Dictionary
A medium Trie interview guide. Task statement, worked examples, intuition, and step-by-step solutions.
- Topic
- Trie
- Sheets
- 1
- Core for
- 7 roles
The problem
Given a list of strings representing a dictionary, find the longest word that can be built one character at a time, with each intermediate prefix also present in the dictionary. If there are ties, return the lexicographically smallest one.
Example 1
- Input
- words = ["c","co","cod","code","coder"]
- Output
- "coder"
- Why
- Every prefix of "coder" is in the list, so it can be built one letter at a time.
Example 2
- Input
- words = ["t","tr","tre","tree","trek","treat","g"]
- Output
- "tree"
- Why
- "tree" and "trek" both build letter by letter; "treat" is missing "trea". Of the two, "tree" comes first alphabetically.
Constraints
- 1 <= words.length <= 10^4
- 1 <= words[i].length <= 30
- words[i] consists of lowercase English letters
How to think about it
Updated 2026-09-29A word qualifies only if every single ancestor node along its path in the trie represents a valid word in the dictionary. If any ancestor lacks a word termination marker, the entire subtree below it is immediately disqualified from being the longest buildable word.
Approaches, worst first
Set membership lookup
time O(n * L^2) · space O(n * L)
Dump all words into a hash set. For each word, check if every prefix from length 1 to L - 1 exists in the set, and maintain the longest lexicographically smallest candidate.
Trie prefix traversalWrite this one
time O(n * L) · space O(n * L)
Insert all words into a trie. Run a depth-first search starting from the root that only traverses child nodes marked as complete words. Traversing alphabet keys in reverse or keeping track of length and lexicographical order yields the optimal word.
Where people lose marks · 3
- Failing to break ties lexicographically when multiple qualifying words achieve the same maximum length.
- Traversing down a branch whose child node is not a terminal word; every step must have isTerminal set to true.
- Returning null or undefined instead of an empty string when no single-letter word exists in the dictionary to begin any sequence.
The theory behind it
Trie — the ground this problem stands on. All Trie problems
What Trie is
A trie, also called a prefix tree, is a tree structured for storing words character by character. Instead of storing entire words in individual nodes, each step down a branch represents a single letter. Words that share the same beginning, like car, card, and care, share the exact same starting path down the tree. A special boolean marker sits at the end of each valid word to show that a complete word terminates at that letter.
When to reach for it
Reach for a trie when questions involve prefix lookups, dictionary word searches, autocomplete engines, or matching prefixes against a body of text. Prompts asking whether any word in a dictionary begins with a given prefix, or searching for words on a Boggle board grid, point directly to a trie. It also applies to bitwise tasks, such as finding the maximum XOR pair among integers by treating numbers as binary prefixes.
How the pattern works
Represent each trie node with an array or hash map of child links, plus a boolean flag marking if a complete word ends at that node. When inserting, start at the root and walk down character by character, creating new child nodes whenever a path does not exist yet, then mark the final node as a word ending. When searching, follow the characters; if any child link is missing, the word or prefix does not exist. If all characters match, check the boolean flag to distinguish between a full word and a partial prefix.
More Trie problems
Target Roles
Core requirement for 7 roles:
Track in your role's order
Pick your target role and all 370 problems resequence to what that interview actually asks.
Start freeProblem set and role mapping as of .