Longest Word with All Prefixes
Among a list of words, find the longest word whose every prefix is also a word in the list. Ties are broken alphabetically.
Open on GeeksforGeeks ↗Intuition
The condition is about every prefix of a word, and a trie is precisely the structure where a word's prefixes are the nodes along its path. Insert everything, flagging each node that terminates a real word. Then a word qualifies if and only if every node on its path carries that flag — one walk per word, no repeated string slicing. Scanning candidates in sorted order makes the tie-break free: the first word to reach a new maximum length is already the alphabetically smallest of that length.
Approach
Build the trie with end flags
Insert every word; mark the final node of each with an end-of-word flag. Shared prefixes share nodes automatically.
Validate by walking
For a candidate word, walk its path and require the end flag at every single node. The first unflagged node disqualifies it immediately.
Sort to make ties free
Process candidates alphabetically and keep a strictly-longer rule. The alphabetical winner is then found without an explicit comparison.
Solution & live demo
Edge cases
Every candidate breaks at some prefix, so the answer is the empty string.
The only prefix is the word itself, so any length-1 word trivially qualifies.
Sorted order visits the alphabetically smaller first, and the strict length comparison prevents the later one from replacing it.