Longest Word with All Prefixes
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.
- 1 <= number of words <= 10⁵
- 1 <= word length <= 30
- Words consist of lowercase English letters
- Ties break lexicographically smallest
Intuition
Longest word with all prefixes asks for the longest word in a list where every prefix of that word is also in the list, with ties broken alphabetically. So "apple" qualifies only if "a", "ap", "app" and "appl" are all present too.
Checking that by slicing each word into prefixes and looking each up in a set works, but it re-derives the same prefixes repeatedly across words that share them.
A trie is the structure where this condition becomes almost free to check, because a word's prefixes are exactly the nodes along its path from the root. Insert every word and flag the node where each one ends. Then:
- A word qualifies precisely when every node on its path carries the end-of-word flag.
One walk per word, no string slicing, and shared prefixes are checked once rather than once per word that contains them. The first unflagged node disqualifies the candidate immediately.
The tie-break comes free with one small choice. Process the candidates in alphabetical order and keep a strictly-longer rule for updating the answer. Then the first word to reach any given length is already the alphabetically smallest of that length, and no explicit comparison is ever written.
That detail is worth noting because the obvious alternative — collecting all qualifying words and sorting at the end — does more work for the same result.
Build a trie of every word, then re-walk each word checking that every node along its path is marked as a word end. That verifies all prefixes exist in one descent instead of doing a separate lookup per prefix. Sorting first makes the lexicographic tiebreak fall out without comparing strings explicitly.
Approach
Before reading on: price up what the direct approach costs here, then ask what the shared prefixes let you avoid storing twice. Aim for O(total characters) time and O(total characters) space.
Insert every word with an end flag
Build a trie from the full list, marking the terminal node of each word. Shared prefixes share nodes automatically, which is why the prefix condition becomes a property of the path rather than a set of separate lookups.
Validate by walking the path
For a candidate, walk its characters from the root and require the end flag at every node, not just the last. The first unflagged node means some prefix is missing from the list, so the word is disqualified.
Fail fast on the first gap
Break out of the walk as soon as a node lacks the flag. Most disqualified words fail within the first few characters, which keeps the average cost far below the word length.
Process candidates alphabetically
Sort the word list before validating. The first word to reach a new maximum length is then already the alphabetically smallest at that length, so the tie-break needs no comparison of its own.
Update only on strictly longer
Keep the answer only when a valid word is strictly longer than the current best. Combined with alphabetical processing, this yields the correct tie-break — using >= instead would let a later, alphabetically larger word of equal length overwrite the right answer.
Cost of the trie approach
Insertion is O(total characters) and each validation walk is O(word length), giving O(total characters) time overall plus O(n log n) for the sort. Space is O(total characters) for the trie nodes.
Solution & live demo
Common pitfalls
Checking each prefix with a separate lookup
if all(w[:i] in word_set for i in range(1, len(w) + 1)):
for ch in w:
node = node[ch]
if "$" not in node: ok = False; breakThat slices and hashes a new string for every prefix — O(L²) per word. Walking the trie visits each prefix's node exactly once as a by-product of the descent.
Ignoring the lexicographic tiebreak
for w in words:
if ok and len(w) > len(best): best = wfor w in sorted(words):
...When several valid words share the maximum length, the problem asks for the lexicographically smallest. Iterating in sorted order means the first one of that length wins and > never replaces it.
Testing the final node only
if "$" in node: ok = True
if "$" not in node:
ok = False
breakThat only confirms the word itself is present, which is trivially true. The requirement is that every prefix is also a word, so the check belongs at each step of the walk.
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.