942. What a Trie Node Costs
Build the trie of n given words and print two numbers: how many nodes it has
including the root, and the largest number of children any single node has.
ab abc -> 4 1
cat car dog -> 8 2
a -> 2 1
ab ac ad ae -> 6 4
Check the second one by hand. The nodes are the root, c, ca, cat, car,
d, do, dog, which is eight. The root has two children (c and d) and
ca has two (t and r), and nothing has three, so the second number is 2.
## Why anyone would want these two numbers
They are the two halves of the memory decision every trie forces.
The node count says how many nodes you will allocate. The largest branching says how full those nodes get. A node stored as a fixed array of 26 child links costs the same whether it uses 26 of them or one.
Take the limits of this problem: 20000 words of at most 20 letters.
raw text 20000 * 20 = 400000 bytes
nodes, worst case 1 + 20000 * 20 = 400001 nodes
26-slot array, 8 bytes a link 26 * 8 = 208 bytes per node
total, array layout 400001 * 208 = 83200208 bytes, about 83 MB
slots that exist 400001 * 26 = 10400026
slots actually used 400000, one per non-root node
So under the worst case for this problem the array layout is about 83 MB and 3.8% of its slots hold anything. A hash map per node stores one entry per edge that exists, which is 400000 entries rather than 10400026 slots, at the cost of a hash on every step instead of an array index.
Neither layout is correct in general. The array is faster and wasteful, the map is compact and slower, and which one you want depends on the branching, which is the second number you are printing.
## The method
Insert every word, creating a node the first time a prefix appears, and count the nodes as you create them. Keep a per-node child counter and increment the PARENT's counter each time you create a child, which costs nothing extra and avoids a second pass over 26 slots per node.
nodes = 1 # the root
for each word w:
node = root
for each letter c of w:
if child[node][c] is absent:
child[node][c] = new node
nodes = nodes + 1
deg[node] = deg[node] + 1
node = child[node][c]
answer = nodes, max over all nodes of deg
## Why repeats and shared prefixes need no special handling
A node is created only the first time a given prefix is seen, and never again,
because the branch that creates it runs only when the child link is absent. So
inserting a word that is already there creates nothing and both counters are
untouched.
a a a gives the same 2 and 1 as a alone. That is the same property problem
939 relies on when it counts distinct prefixes.
## The off-by-one
The root is a node and it is counted, but the root is not a prefix of anything: it is the EMPTY prefix. So this node count is exactly one more than the answer to problem 939, which counts distinct non-empty prefixes and therefore excludes it. Getting this wrong is the single likeliest mistake here.
## Overflow
Nothing here overflows. The largest value is the slot count you might compute on paper, 400001 * 26 = 10400026, which is far inside a signed 32 bit integer, and the two printed numbers are at most 400001 and 26.
Constraints - `1 ≤ n ≤ 20000` - Every word is 1 to 20 lowercase English letters. - Words may repeat.
Input
The first line contains an integer n.
The next n lines each contain one word.
Output
Print two integers on one line separated by a single space: the number of nodes in the trie including the root, and the largest number of children held by any one node.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.