Stateful Search Autocomplete Session

Design a search-autocomplete session over historical sentences and their search counts: sentences[i] was searched times[i] times. The user then types one character at a time.

AutocompleteSystem(sentences, times)
input(c) -> string[]

Each c is a lowercase letter, a space, or "#":

• c != "#": append c to the current query and return the top 3 historical sentences whose prefix equals everything typed so far — ordered by frequency descending, ties broken lexicographically ascending (ASCII, so space sorts before "a"). Fewer than 3 if fewer match; [] if none.
• c == "#": the query typed so far is a finished sentence. Record it (frequency + 1; a never-seen sentence starts at 1), reset the session, and return []. A bare "#" with nothing typed records nothing.

s = new AutocompleteSystem(["i love you", "island", "iroman", "i love leetcode"],
                           [5, 3, 2, 2])
s.input("i")  => ["i love you", "island", "i love leetcode"]
                 ("iroman" ties "i love leetcode" at 2; the latter sorts first)
s.input(" ")  => ["i love you", "i love leetcode"]
s.input("a")  => []
s.input("#")  => []          "i a" is stored with frequency 1
s.input("i")  => ["i love you", "island", "i love leetcode"]
s.input(" ")  => ["i love you", "i love leetcode", "i a"]

Up to 100 initial sentences, length <= 100, up to 5000 input() calls.

Follow-ups

• Make input(c) cheaper than rescanning every sentence — where does the time go?
• Generalize to top-k.
• The user types a prefix nothing matches — avoid wasted work for the rest of that query.