Topics

# Auto Suggestion

Hard
0/120
Average time to solve is 60m
Contributed by
+1 more companies

## Problem statement

Bob had a hard time remembering the spelling of words. Alice, his best friend, decided to make a program that suggests words after every character Bob types.

Alice had an array of ‘N’ strings ‘S’ containing Bob’s most commonly used words. She decided to suggest at most three words after each character is typed. The typed word and the suggested word should have the same prefix. If there are more than 3 such words in the array, print the three lexicographically minimum words.

Detailed explanation ( Input/output format, Notes, Images )
Constraints:
``````1 <= T <= 10
1 <= N <= 1000
1 <= L <= 1000
1 <= Sum of lengths of all ‘S[i]’ <= 2 * 10 ^ 4.
There are no repeated elements in the array ‘S’.
All characters in ‘S[i]’ and ‘P’ are lower-case English letters.

Time Limit: 1 sec
``````
Sample Input 1:
``````2
4
abc ab aa a
3
abc
3
na bw a
3
abc
``````
Sample Output 1:
``````a aa ab
ab abc
abc
a
``````
Explanation for Sample Input 1:
``````In the first test case, after Bob types ‘a’, the program suggests ‘a aa ab’. After typing ‘ab’ , the program suggests ‘ab abc’, and after typing ‘abc’ the program suggests ‘abc’.
In the second test case, after Bob types ‘a’, the program suggests ‘a’ but after typing ‘ab’ and ‘abc’, the program suggests noting.
``````
Sample Input 2:
``````2
2
cn cnn
1
c
1
roll
4
roll
``````
Sample Output 2:
``````cn cnn
roll
roll
roll
roll
``````
Console