Log inSign up
mediumLeetCodeNot Started

Longest Word in Dictionary

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Trie
Solve on LeetCode
Lesson

Problem Statement

Given an array of strings words representing an English Dictionary, return the longest word in words that can be built one character at a time by other words in words.

If there is more than one possible answer, return the longest word with the smallest lexicographical order. If no answer exists, return the empty string "".

Example 1 · Example 1: Word chain:

Input: words = ["w","wo","wor","worl","world"]
Output: "world"
Explanation: The word "world" can be built one character at a time: "w" -> "wo" -> "wor" -> "worl" -> "world". Trie Path: (root) | w* (isEnd) | o* (isEnd) | r* (isEnd) | l* (isEnd) | d* (isEnd -> "world")

Example 2 · Example 2: Lexicographical tie-break:

Input: words = ["a", "banana", "app", "appl", "ap", "apply", "apple"]
Output: "apple"
Explanation: Both "apply" and "apple" can be built from other words. Both have length 5, but "apple" is lexicographically smaller than "apply".

Constraints:

  • 1 <= words.length <= 1000
  • 1 <= words[i].length <= 30
  • words[i] consists of lowercase English letters.

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Formulate prefix dependency problems as reachability queries in a Trie.
  • Traverse only active Trie branches where isEnd == true.
  • Resolve multi-criteria tie-breakers (maximum length, smallest lexicographical) elegantly.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Problem requires checking whether every prefix of a candidate word exists in the dataset.
  • Maximizing length with lexicographical tie-breaker.
  • Incremental word construction character by character.

Algorithmic Decision Tree:

  • Build a Trie of all words, setting isEnd = true and storing the word string at terminal nodes.
  • Execute DFS/BFS from root: only expand child nodes that have isEnd == true.
  • Track the longest word seen; if lengths tie, lexicographical comparison breaks the tie.

Connected Patterns:

Implement Trie (Prefix Tree)Word Search IILongest Common Prefix

1. Hash Set Prefix Verification for All Words

Intuition

Insert words into unordered_set<string>. For each word, check set.count(word.substr(0, k)) for k from 1 to word.length(). If all exist, compare with current best (longer length, or smaller lexicographical).

When to apply: Quick brute force baseline.

Algorithm

  1. Step 1: Insert all words into an unordered set.
  2. Step 2: Initialize best = "".
  3. Step 3: For each word in words: check if all prefixes exist in the set.
  4. Step 4: If valid, update best if word.length() > best.length() or (word.length() == best.length() && word < best).
  5. Step 5: Return best.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <vector>
4#include <unordered_set>
5using namespace std;
6
7class Solution {
8public:
9 string longestWord(vector<string>& words) {
10 unordered_set<string> dict(words.begin(), words.end());
11 string best = "";
12
13 for (const string& w : words) {
14 bool valid = true;
15 for (size_t k = 1; k < w.length(); k++) {
16 if (!dict.count(w.substr(0, k))) {
17 valid = false;
18 break;
19 }
20 }
21 if (valid) {
22 if (w.length() > best.length() || (w.length() == best.length() && w < best)) {
23 best = w;
24 }
25 }
26 }
27 return best;
28 }
29};
30
31int main() {
32 Solution sol;
33 vector<string> words = {"w","wo","wor","worl","world"};
34 cout << "Longest word: " << sol.longestWord(words) << endl;
35 return 0;
36}

Time & Space Complexity

  • Time complexity: O(N * L^2) — Generates L substrings per word, taking O(L2) time for N words.
  • Space complexity: O(N * L) — Stores all words in the hash set.

Why Brute Force Doesn't Scale:

With 1,000 words of length 30, brute force checks 30,000 prefixes via hash table lookups.

Trie DFS navigates only the valid subgraph in a single pass of O(Total characters * 26).

2. Sorting by Length & Custom Comparator with Set

Intuition

Sort words by length ascending; if lengths match, sort lexicographically descending. Maintain validWords set initialized with "". If word.substr(0, len-1) is in validWords, add word and update best = word.

When to apply: Compact code avoiding explicit Trie allocation.

Algorithm

  1. Step 1: Sort words: len(a) < len(b) or (len(a) == len(b) && a > b).
  2. Step 2: Initialize built = {""}, best = "".
  3. Step 3: Loop through sorted words: if word.substr(0, word.length() - 1) in built: insert word into built, update best = word.
  4. Step 4: Return best.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <vector>
4#include <unordered_set>
5#include <algorithm>
6using namespace std;
7
8class Solution {
9public:
10 string longestWord(vector<string>& words) {
11 sort(words.begin(), words.end(), [](const string& a, const string& b) {
12 if (a.length() != b.length()) return a.length() < b.length();
13 return a > b; // reverse lexicographical for equal length
14 });
15
16 unordered_set<string> built = {""};
17 string best = "";
18
19 for (const string& w : words) {
20 if (built.count(w.substr(0, w.length() - 1))) {
21 built.insert(w);
22 best = w;
23 }
24 }
25 return best;
26 }
27};
28
29int main() {
30 Solution sol;
31 vector<string> words = {"a", "banana", "app", "appl", "ap", "apply", "apple"};
32 cout << "Best buildable word: " << sol.longestWord(words) << endl;
33 return 0;
34}

Time & Space Complexity

  • Time complexity: O(N log N * L) — Sorting N strings takes O(N log N * L). Single pass takes O(N * L).
  • Space complexity: O(N * L) — Set stores all valid buildable words.

3. Trie DFS with isEnd Constrained Traversal

Intuition

Insert words into Trie. Each node stores children[26], isEnd, and the complete word string. From root, run DFS. Only visit children where child != null && child.isEnd == true. Children are traversed a through z, naturally resolving ties.

When to apply: Standard optimal solution with zero sorting overhead.

Algorithm

  1. Step 1: Define TrieNode with children[26], word = "", isEnd = false.
  2. Step 2: Insert all words into Trie, storing full word at terminal node.
  3. Step 3: DFS helper starting from root. Maintain bestWord.
  4. Step 4: If current node has a valid word, update bestWord if longer or tie-break smaller.
  5. Step 5: Iterate child 0..25: if child && child.isEnd, recurse.
  6. Step 6: Return bestWord.

Interactive DFS Trace on Buildable Trie Nodes

2 of 2 questions left today
Step 1 / 3
Trace timeline33% explored
Current operationSTEP 1 OF 3
Step 1: Start at root
Visual state
Values and pointers at this exact step
tree
Root
(root)
char 'a'*
'a'* (isEnd)

Node order shown; add connections to display explicit tree edges.

curr: a
Check / comparison
child['a'].isEnd == true
Decision / next transition
Advance to node 'a', update result to 'a'.
Why this step matters

Step 1: Start at root. Child a has isEnd = true. Recurse to node a. Current best = a.

Step 1 / 3
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <vector>
4using namespace std;
5
6struct TrieNode {
7 TrieNode* children[26];
8 string word;
9 bool isEnd;
10
11 TrieNode() : word(""), isEnd(false) {
12 for (int i = 0; i < 26; i++) children[i] = nullptr;
13 }
14};
15
16class Solution {
17 TrieNode* root;
18 string bestWord;
19
20 void insert(const string& w) {
21 TrieNode* curr = root;
22 for (char c : w) {
23 int idx = c - 'a';
24 if (!curr->children[idx]) curr->children[idx] = new TrieNode();
25 curr = curr->children[idx];
26 }
27 curr->isEnd = true;
28 curr->word = w;
29 }
30
31 void dfs(TrieNode* node) {
32 if (!node) return;
33 if (!node->word.empty()) {
34 if (node->word.length() > bestWord.length() ||
35 (node->word.length() == bestWord.length() && node->word < bestWord)) {
36 bestWord = node->word;
37 }
38 }
39
40 for (int i = 0; i < 26; i++) {
41 if (node->children[i] && node->children[i]->isEnd) {
42 dfs(node->children[i]);
43 }
44 }
45 }
46
47public:
48 string longestWord(vector<string>& words) {
49 root = new TrieNode();
50 bestWord = "";
51
52 for (const string& w : words) insert(w);
53 dfs(root);
54 return bestWord;
55 }
56};
57
58int main() {
59 Solution sol;
60 vector<string> words = {"a", "banana", "app", "appl", "ap", "apply", "apple"};
61 cout << "Optimal longest buildable word: " << sol.longestWord(words) << endl;
62 return 0;
63}

Time & Space Complexity

  • Time complexity: O(Sum of word lengths * 26) — Building Trie is linear in total characters. DFS visits each buildable node at most once.
  • Space complexity: O(Sum of word lengths * 26) — Trie nodes allocate 26 pointers each.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Sort and Hash Set Prefix ValidationO(N log N + N * L^2)O(N * L)Insert all words into a hash set. For each word, verify if all its prefixes exist in the set. Track longest word.String slicing and hashing for all prefixes of each word.
2.Better — Sort by Length and Alphabetical OrderO(N log N * L)O(N * L)Sort words so smaller length comes first, and equal lengths are sorted in reverse lexicographical order. Build valid words set incrementally.Sorting N strings with custom comparator.
3.Optimal — Trie with Prefix-Constrained DFSOptimalO(Sum of word lengths * 26)O(Sum of word lengths * 26)Insert all words into Trie. DFS from root, only stepping into child nodes that have isEnd == true.None. Classical optimal interview solution.

Common Pitfalls & Crucial Edge Cases

Traversing children without checking `child.isEnd`

Explores words whose intermediate prefixes are missing.

Forgetting lexicographical tie-breaker

Failing when two buildable words share maximum length.

Storing string slices during DFS

Re-slicing strings at each node wastes heap memory; storing node.word directly avoids all slicing.

Crucial Edge Cases to Validate:

  • No 1-letter words in dictionary — No word can be built. Correctly returns empty string "".
  • Multiple words with equal length and buildability — Lexicographically smallest word wins ("apple" vs "apply").
  • Disjoint word chains — Only chains rooted at a 1-letter word with valid isEnd are explored.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Explain the reachability invariant: a word is buildable if and only if every node on its Trie path has isEnd == true.
  2. Mention storing the complete word string directly at the terminal Trie node so path reconstruction takes O(1).
  3. Discuss BFS vs DFS: BFS level-by-level with a queue is an equally valid approach.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why does the optimal DFS only visit children where child.isEnd == true?

2.How is the lexicographical tie-breaker naturally resolved in the Trie approach?

Back to DSA Sheet