951. The Longest Word You Can Grow One Letter at a Time
You are given n distinct words. Find the longest word that can be built up one
letter at a time, where every intermediate string is also one of the given words.
That is, a word w qualifies when every non-empty proper prefix of w is in the
list. If several qualify at the same greatest length, print the alphabetically
smallest. If none qualifies, print none.
A one letter word has no non-empty proper prefix, so it always qualifies.
a ab abc ba bad b -> abc abc and bad both work, abc sorts first
w wo wor world -> wor world fails because worl is missing
xy yz -> none neither x nor y is in the list
b ba bat c ca cat cats -> cats
## The shape of the answer in the trie
Insert every word. A word qualifies exactly when every node on its path from the root, apart from the root, is marked as the end of a word.
So mark the ends, then explore only through marked nodes: from any node, step into a child only if that child is marked. Every path reachable that way is a qualifying word, and every qualifying word is such a path.
best = ""
dfs(node, path):
if length(path) > length(best): best = path
for c in a .. z:
nxt = child[node][c]
if nxt exists and isEnd[nxt]:
dfs(nxt, path + c)
print best if it is non-empty, else "none"
## Why the tie is broken for free
Visiting children in the order a to z means the search reaches candidates in
alphabetical order. Using a STRICT comparison, length(path) > length(best),
means the first word reached at any given length keeps the title and no later
word of equal length can take it. Together those give "longest, then
alphabetically smallest" without a single comparison of two words.
Switching the test to >= silently breaks the tie the other way and returns the
alphabetically LARGEST of the longest, which on z za zb zc turns za into
zc.
## Why pruning at the first unmarked node loses nothing
If a node on a path is not marked, that string is not one of the given words, so no word extending past it can qualify either: every longer word has that string as a proper prefix. Refusing to descend is therefore not an optimisation, it is the definition, and it is what keeps the search inside the answer set instead of inside the whole trie.
## The boundary that catches people
The root must not be required to be marked, because the empty string is not one
of the given words and never will be. Requiring it makes every answer none.
Equally, the word itself does not need to be checked against the list, since it
is in the list by construction; only its PROPER prefixes matter, which is why
one letter words qualify with nothing to check.
## Cost
Building is O(total characters). The search visits each node at most once, so
it is O(nodes * 26), at most 400001 nodes here. The recursion is at most 20
deep, one level per letter.
## Against problem 944
944 walks the whole trie to list every word in order. This walks the same way but refuses to leave the marked nodes, which is how a traversal turns into a search.
Constraints - `1 ≤ n ≤ 20000` - Every word is 1 to 20 lowercase English letters. - The words are pairwise different.
Input
The first line contains an integer n.
The next n lines each contain one word. The words are all different.
Output
Print one line holding the longest word all of whose non-empty proper prefixes are also in the list, choosing the alphabetically smallest if several tie, or the word none if no word qualifies.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.