p104 — Design Autocomplete System — Hints

1. It’s a state machine, not a one-shot query. input(c) builds up a buffer over many calls. You need self.buf: str and self.cur: Optional[Node] as instance state. Reset both on '#'.

2. Trie node holds frequency at the terminal (or as count at every internal sentence-end). Insert a sentence by descending one char at a time, then += freq on the terminal node’s count field.

3. Tie-break is (-frequency, sentence), not (-frequency, -sentence). Frequencies sort descending, sentences sort ASCENDING on ties. Easiest: collect all candidates from the subtree, sort with key=lambda x: (-x[1], x[0]), take first 3.

4. Off-trie behavior. If self.cur is None (we’ve already gone off-trie this query), or if the next char has no child, set self.cur = None and return []. Stay off-trie until '#' arrives — don’t try to re-find a matching prefix mid-stream.

5. '#' commits the current buffer. Increment count if the sentence already exists; insert with count 1 if new. Then reset state. The buffer can contain spaces (treat them as ordinary characters).

If stuck: see solution.py.