Search Autocomplete with Trie

Design a search autocomplete system for a search engine. Users may input a sentence (at least one word and end with a special character '#'). For each character they type except '#', you need to return the top 3 historical hot sentences that have the same prefix as the part of the sentence already typed. Here are the specific rules:

1. The hot degree for a sentence is defined as the number of times a user typed the exact sentence.
2. The returned top 3 hot sentences should be sorted by hot degree (first by frequency in descending order, then lexicographically in ascending order if frequencies tie).
3. When the input is a special character '#', it means the user finishes the input, and you should store the exact sentence and update its frequency.

You need to implement the AutocompleteSystem class with the following methods:

• AutocompleteSystem(String[] sentences, int[] times): This is the constructor. The input is historical data. Sentences is a string array consisting of previously typed sentences. Times is the corresponding times each sentence has been typed. The system should use this data to give suggestions.
• List<String> input(char c): This represents the user inputting a character. The output should be the top 3 historical hot sentences with the same prefix as the current input string. If the character is '#', the current input should be stored and the suggestions list should be empty.