Implementation considerations:
Track current input: accumulate typed characters until '#'
Update on '#': insert the completed sentence into trie, increment frequency
Maintain sorted suggestions: use heap or sorted insertion
Handle special characters: spaces are valid characters in sentences
function input(c):
if c == '#':
this.insert(this.currentInput)
this.currentInput = ""
return []
this.currentInput += c
node = this.findNode(this.currentInput)
if node == null:
return []
return top 3 suggestions from node.suggestions
This problem is complex because it combines trie operations with ranking and stateful input handling.