System Design — Search Autocomplete

Type a few characters and get the three most popular completions — Google's search box in
miniature.

solve(args, ops) builds new Autocomplete(sentences, times) — args = [sentences, times];
times[i] is how many times sentences[i] has already been searched — and replays ops:

• input(c) — the user typed one character c:

- if c is "#", the sentence typed so far is submitted: add one to its count (create it
with count 1 if new), reset the typed text and return [];
- otherwise append c to the typed text and return the top 3 known sentences that start
with it, as an array.

Ordering is pinned: higher count first; ties are sorted ascending by plain ASCII order of
the whole sentence (so a space sorts before any letter). Return fewer than 3 if fewer match.

Scanning every sentence per keystroke is fine here. At scale you would keep a trie whose
nodes cache their best suggestions.

Example — sentences = ["i love you","island","iroman","i love leetcode"], times = [5,3,2,2]

input("i") → ["i love you","island","i love leetcode"]
input(" ") → ["i love you","i love leetcode"]
input("a") → []     input("#") → []