Search Suggestion Service

Design and implement a prefix search suggestion service, typically with a trie and top-K ranking by frequency and lexicographic tie-break. Requirements Implement an autocomplete / search suggestion class. A common API is: class AutocompleteSystem: def __init__(self, sentences: list[str], times: list[int]): ... def input(self, c: str) -> list[str]: ... Expected behavior: Maintain a current query prefix as characters arrive. For each non-terminal character, return up to 3 matching suggestions. Rank suggestions by descending frequency, then lexicographic / ASCII order for ties. When the terminal character is entered, store the completed sentence and increment its count. Support repeated queries without corrupting trie state. Notes The standard implementation uses a trie. Each trie node either stores all sentence candidates under that prefix or points to children and performs DFS at query time. Storing candidates in each node makes query fast at the cost of higher update work; DFS keeps storage lower but can be too slow for broad prefixes. For interviews, a practical design stores a map of sentence counts globally and a candidate set or map at each trie node. On each completed sentence, insert it through the trie and update the candidate metadata along the path. At query time, sort candidates by (-count, sentence) and return the first three, or maintain a small top-K structure per node if update performance matters. Preparation Implement the LC 642 API once using trie nodes with candidate maps. Test '#' submission, repeated sentence updates, no-match prefixes, and lexicographic tie-breaks. Practice discussing the update/query/storage trade-off for candidate lists at each trie node.