Implement a search autocomplete suggestion service

Design an autocomplete component that suggests the most relevant search phrases as a user types.

You are given historical sentences with their usage counts. The system receives the query one character at a time and must return suggestions after each character.

Requirements

• Initialize with:
  • sentences[i] : a previously typed sentence
  • times[i] : how many times it was typed
• On each input character c :
  • If c != '#' , append it to the current query prefix and return the top 3 matching historical sentences that start with this prefix.
  • If c == '#' , treat the current query as a completed sentence:
    • increment its count by 1 (add it if new)
    • clear the current query
    • return an empty list

Ranking

• Higher count ranks first.
• Ties are broken by lexicographically smaller sentence first.

API

Implement a class with methods:

• AutocompleteSystem(sentences, times)
• input(c) -> List[str]

Constraints (reasonable interview constraints)

• Number of historical sentences: up to 2 * 10^4
• Sentence length: up to 100
• Number of input() calls: up to 2 * 10^4