Store sentences in a trie. At each node, maintain a sorted list of top sentences passing through. class TrieNode: children: map suggestions: list of (sentence, count) sorted by (-count, sentence) When inserting a sentence:
Update the count in the trie
For each node along the path, update its suggestions list When querying prefix:
move through to prefix node
Return top 3 from node's suggestions list Trade-off: storing suggestions at each node uses more space but makes queries instead of traversing subtrees. Alternative: only store at end nodes, then collect and sort during query. Better space, worse query time. Time: . Space: .