Design a search autocomplete system. For each character you type, return the top 3 historical sentences that have the prefix.
Sentences are ranked by frequency (times searched). If frequencies are equal, use lexicographic order.
Example:
input("i") → ["i love you", "island", "i love coding"]
input(" ") → ["i love you", "i love coding"]
input("a") → ["i a"]
input("#") → [] (# means end of input)
You're building a realistic autocomplete problem combining tries with frequency counting.
Constraints: up to 100 historical sentences, each with length up to 100.