Problem Challenge: Search Auto-Complete Optimized

Problem statement

We're provided with a list of keywords and a query string. Design a system that provides the top three suggestions from the keyword list to the user every time the user types a character of the query string.

The suggested words should be a prefix of the query string typed so far. If there are more than three valid suggestions, return the three lexicographically smallest ones. For a better user experience, we want to serve these suggestions quickly.

Example

Sample input