Definition
- Longest buildable word – finds the longest word from a list where every prefix of that word is also a word in the list.
- Trie construction – insert all words into a trie, marking each word's end node.
- Word-only DFS – traverse the trie from the root, only stepping into children that are marked as complete words.
- Tie-breaking – among words of equal length, the lexicographically smallest wins; visiting children in sorted order handles this.
- Complexity – O(sum of all word lengths) for both construction and traversal.
The National Bank of India builds product feature codes incrementally, where each longer code must extend a code that already exists. Rajesh wants the longest code reachable by adding one character at a time, with every intermediate code being a valid registered code.
Understanding the Concepts
What is the Longest Word in Dictionary problem?
Given a list of words, find the longest word that can be built one character at a time by adding one letter to the end, where every intermediate string is also a word in the list. If there are ties, return the lexicographically smallest. For example, given ["A", "AP", "APP", "APPL", "APPLE", "B", "BA", "BAT"], the answer is "APPLE" because every prefix ("A", "AP", "APP", "APPL") is also in the list.
package com.bank.core;
// Words: ["A", "AP", "APP", "APPL", "APPLE", "B", "BA", "BAT"]
// "APPLE" -> prefixes: "A", "AP", "APP", "APPL" -> all in the list
// "BAT" -> prefixes: "B", "BA" -> all in the list, but length 3 < 5
// Answer: "APPLE"
Why use a trie?
The key insight is that a word is buildable one character at a time exactly when every node on its path from the root is marked as a complete word. A trie naturally represents this: after inserting all words and marking their end nodes, you traverse the trie from the root and only descend through nodes that are marked as words. This ensures every prefix is valid.
package com.bank.core;
// Trie after inserting ["A", "AP", "APP"]:
// root -> A[word] -> P[word] -> P[word]
// DFS from root: A is a word -> descend
// A -> P is a word -> descend
// AP -> P is a word -> descend
// APP is reachable with all-word path, length 3
How do you implement it?
Build the trie by inserting all words. Then run a DFS from the root, only stepping into children that are marked as complete words. Track the longest word found, breaking ties by lexicographic order.
package com.bank.service;
public class LongestWordInDictionary {
private static class TrieNode {
TrieNode[] children = new TrieNode[26];
String word = null;
}
private TrieNode root = new TrieNode();
private String best = "";
public String longestWord(String[] words) {
// Build trie
for (String w : words) {
TrieNode node = root;
for (char c : w.toCharArray()) {
int idx = c - 'a';
if (node.children[idx] == null) {
node.children[idx] = new TrieNode();
}
node = node.children[idx];
}
node.word = w;
}
// DFS only through word nodes
best = "";
dfs(root);
return best;
}
private void dfs(TrieNode node) {
for (int i = 0; i < 26; i++) {
TrieNode child = node.children[i];
if (child != null && child.word != null) {
// This child is a complete word -> descend
if (child.word.length() > best.length()) {
best = child.word;
}
dfs(child);
}
}
}
public static void main(String[] args) {
LongestWordInDictionary solver = new LongestWordInDictionary();
System.out.println(solver.longestWord(
new String[]{"a", "ap", "app", "appl", "apple",
"b", "ba", "bat"}));
System.out.println(solver.longestWord(
new String[]{"w", "wo", "wor", "worl", "world"}));
}
}
apple
world
How does the DFS enforce the buildable rule?
The DFS only enters a child node if it is marked as a complete word. This means every node on the path from root to the current position represents a valid word in the list. If any intermediate prefix is missing, that node will not be marked as a word, and the DFS will not descend through it, stopping the path.
package com.bank.core;
// Words: ["A", "APP"] (missing "AP")
// Trie: root -> A[word] -> P[not word] -> P[word]
// DFS: root -> A (word, descend)
// A -> P (NOT a word, do not descend!)
// "APP" is never reached because "AP" is missing
// This correctly enforces the one-char-at-a-time rule
How do you handle the lexicographic tie-break?
By iterating over children in order from index 0 (character 'a') to index 25 (character 'z'), the DFS visits lexicographically smaller children first. When two words have the same length, the first one found (the lexicographically smaller one) is kept because the update condition checks strictly greater length.
package com.bank.core;
// Words: ["a", "ab", "ac"]
// Both "ab" and "ac" have length 2
// DFS visits 'b' before 'c' (index order)
// "ab" is found first, best = "ab"
// "ac" has same length, 2 > 2 is false, best stays "ab"
// Correct: "ab" < "ac" lexicographically
What are the edge cases?
Edge cases include: no word of length 1 (no word is buildable, return empty), all single-character words, duplicate words in the list, and very long chains.
package com.bank.core;
// Edge case 1: no single-char words -> no word is buildable, return ""
// Edge case 2: ["a", "b", "c"] -> longest buildable is "a" (or "b" or "c")
// with tie-break: "a" (smallest)
// Edge case 3: ["a", "a"] -> duplicates handled by trie naturally
// Edge case 4: ["a","ab","abc",...,"abcdef..."] -> long chain
What about using BFS instead of DFS?
BFS from the root is an alternative: enqueue children that are complete words, processing level by level. The last word dequeued at the deepest level is the answer (with appropriate tie-break). BFS naturally finds the longest path because it processes shorter words first.
package com.bank.service;
import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;
public class LongestWordBFS {
public String longestWord(String[] words) {
Arrays.sort(words); // sort for tie-break
Set<String> built = new HashSet<>();
built.add(""); // empty string is trivially buildable
String best = "";
for (String word : words) {
String prefix = word.substring(0, word.length() - 1);
if (built.contains(prefix)) {
built.add(word);
if (word.length() > best.length()) {
best = word;
}
}
}
return best;
}
}
What about a banking use case?
At the National Bank of India, product feature codes are built incrementally. A longer code is only valid if every shorter prefix is a registered code. Rajesh finds the longest valid code chain.
package com.bank.service;
public class FeatureCodeChain {
private final LongestWordInDictionary solver = new LongestWordInDictionary();
public String findLongestChain(String[] registeredCodes) {
String longest = solver.longestWord(registeredCodes);
System.out.println("Longest buildable code: " + longest);
return longest;
}
public static void main(String[] args) {
FeatureCodeChain chain = new FeatureCodeChain();
chain.findLongestChain(new String[]{
"p", "pa", "pay", "paym", "payme", "paymen", "payment"});
}
}
Longest buildable code: payment
What should a senior engineer know?
A senior engineer should know that this is a traversal application of the Trie pattern, distinct from search applications like Word Search II. The word-only descent rule is the structural encoding of the buildable constraint, and sorted child traversal handles the tie-break cleanly. The alternative sort-and-set approach is simpler but uses more space; the trie approach is more efficient for large dictionaries.
package com.bank.core;
// Senior notes:
// 1. Trie traversal, not search: the constraint is structural
// 2. Word-only descent = buildable-one-char-at-a-time constraint
// 3. Sorted child iteration = free lexicographic tie-break
// 4. Time: O(total characters) for build + traverse
// 5. Alternative: sort words + HashSet of buildable, O(n*L*log(n))
Visual Overview
Trie for words: ["a", "ap", "app", "appl", "apple", "b", "ba", "bat"]
root
/ \
a[w] b[w]
| |
p[w] a[w]
| |
p[w] t[w]
|
l[w]
|
e[w] = "apple"
[w] = marked as a complete word
DFS (word-only descent):
┌──────────────────────────────────────────┐
│ root -> 'a' (word) -> descend │
│ 'a' -> 'p' (word) -> descend │
│ 'ap' -> 'p' (word) -> descend │
│ 'app' -> 'l' (word) -> descend │
│ 'appl' -> 'e' (word) -> descend │
│ 'apple' -> no more children │
│ best = "apple" (length 5) │
│ │
│ root -> 'b' (word) -> descend │
│ 'b' -> 'a' (word) -> descend │
│ 'ba' -> 't' (word) -> descend │
│ 'bat' -> no more children │
│ "bat" length 3 < 5, no update │
└──────────────────────────────────────────┘
Result: "apple" (length 5 > "bat" length 3)
Key Takeaway
Longest Word in Dictionary asks for the longest word from a list where every prefix of that word is also present in the list. This is a traversal application of the Trie pattern. After inserting all words and marking their end nodes, you traverse the trie from the root and only descend through nodes that are marked as complete words. If any intermediate prefix is missing, the DFS stops, correctly enforcing the one-character-at-a-time buildable rule.
The tie-break for lexicographic order comes free by iterating over children in sorted character order (index 0 to 25). Among words of equal length, the first one found in this sorted traversal is the lexicographically smallest. The update condition checks strictly greater length, so the first maximum-length word found is kept.
The time complexity is O(total characters) for trie construction and traversal, and the space is proportional to the total characters stored in the trie. An alternative approach sorts the words, then builds a set of buildable words by checking whether each word's prefix (minus the last character) is already in the set. This is simpler but requires sorting and uses a hash set.
At the National Bank of India, product feature codes are built incrementally, and a longer code is only valid if every shorter prefix is already registered. Rajesh used the trie approach to find the longest valid code chain, and the word-only descent rule naturally enforced the incremental-building constraint.
Remember one sentence: insert all words into a trie, then DFS only through nodes marked as complete words to find the longest path where every prefix is a valid word.
---