946. Deleting a Word Without Losing the Others

Run q operations against a set of words.

add w put w in the set; if it is already there, nothing changes del w take w out of the set; if it is not there, nothing changes find w print yes if w is in the set, else no

After every del, every node that no longer has any word of the set below it must be REMOVED from the trie. After the last operation, print how many nodes the trie still holds, not counting the root.

``` add cat, add car, find cat, del cat, find cat, find car, add cat -> yes, no, yes, and 4 nodes at the end (c, ca, cat, car)

add ab, add abc, del abc, find ab, find abc -> yes, no, and 2 nodes (a, ab)

add ab, add abc, del ab, find ab, find abc, del abc -> no, yes, and 0 nodes ```

The last two lines are the pair to study. Deleting abc when ab is still stored removes exactly one node. Deleting ab when abc is still stored removes NONE, because every node on ab's path is still carrying abc.

## Why adding a flag is easy and removing one is not

Insertion only ever creates. Deletion has to decide, at every node on the path, whether that node is still wanted, and the answer depends on the whole subtree below it, which is not information a plain trie node carries.

The tempting shortcut is to clear the end flag and stop. That is correct for find and wrong for the node count, and it leaks: a program that adds and deletes 20000 words of 20 letters keeps up to 400000 dead nodes, at 208 bytes each under the 26-slot layout, which is 83200000 bytes of trie holding nothing.

The other tempting shortcut is to delete the whole path. That is simply wrong: it would remove ab when abc is deleted, and the third example above shows a case where nothing may be removed at all.

## Carry a subtree count

Give every node a counter cnt holding how many words of the set lie at or below it. Insert increments it along the path, delete decrements it.

``` add w: if w is already present: stop walk w creating missing nodes, cnt[node] += 1 at each step isEnd[last] = true

del w: if w is not present: stop record the path root = v0, v1, ... vL isEnd[vL] = false cnt[vk] -= 1 for k = 1 .. L find the SMALLEST k >= 1 with cnt[vk] == 0 if one exists: cut the link from v(k-1) to vk L - k + 1 nodes have just left the trie ```

## Why cutting one link removes exactly the right nodes

Keep the invariant that every node in the trie has cnt at least 1. Suppose after the decrements cnt[vk] is 0. Any child of vk that is NOT on this path was untouched by the decrements, so it still has cnt at least 1, and then cnt[vk] would be at least 1 too. Contradiction. So vk's only descendants are v(k+1) .. vL, all of which are also at 0 because cnt never increases going down. Cutting the one link therefore removes exactly L - k + 1 nodes and nothing else, and the invariant holds again.

That is why a single cut is enough and no recursive sweep is needed.

## The two guards that are easy to forget

add of a word already present must change nothing, or cnt is inflated along the path and the node count never returns to 0. del of a word that is not present must change nothing, and note that reaching the word's last node is NOT the same as the word being present: after add abc, the word ab has a node but no end flag, so deleting it must be a no-op.

## Cost

Every operation costs the length of its word. The total node count printed at the end is maintained as a running total, adjusted by one on each creation and by L - k + 1 on each cut, so no final scan is needed.

## Against problem 947

947 keeps a multiset and answers how many stored words sit under a prefix, so it decrements counts too but never removes a node. Here the removal is the whole question, which is why the node count is part of the output.

Constraints - `1 ≤ q ≤ 20000` - Every `w` is 1 to 20 lowercase English letters. - An `add` of a word already in the set, and a `del` of a word not in the set, are both legal and change nothing.