Search Auto-complete

Problem statement

Auto-complete is a feature—similar to one provided by search engines—that displays query suggestions in real time based on what search string a user is typing in the input field.

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.

Example

Sample input