Search Suggestions System
01 · Problem
You are building autocomplete for a store. Given an array of strings products and a string searchWord, simulate the user typing searchWord one character at a time.
After each character is typed, the current prefix is the first i characters of searchWord. Suggest at most three products that start with that prefix. If more than three products match, return the three that are lexicographically smallest, in ascending lexicographic order. If none match, return an empty list for that step.
Return a list of searchWord.length lists, one per typed character, in typing order.
02 · Examples
products = ["apple","apricot","banana","app","apex"], searchWord = "apr"
[["apex","app","apple"],["apex","app","apple"],["apricot"]]
Sorted products are apex, app, apple, apricot, banana. Prefixes "a" and "ap" both match the first four, so the first three are returned. Only "apricot" matches "apr".
products = ["kiwi"], searchWord = "kix"
[["kiwi"],["kiwi"],[]]
"kiwi" matches "k" and "ki", but no product starts with "kix", so the last list is empty.
products = ["bag","baggage","banner","box","cloth"], searchWord = "bags"
[["bag","baggage","banner"],["bag","baggage","banner"],["bag","baggage"],[]]
"b" matches four products; the three smallest are bag, baggage, banner. "ba" matches the same three. "bag" matches bag and baggage, and nothing starts with "bags".
03 · Constraints
- 011 <= products.length <= 1000
- 021 <= products[i].length <= 3000
- 031 <= searchWord.length <= 1000
- 04products[i] and searchWord consist of lowercase English letters
- 05All strings in products are unique
04 · Optimal complexity
- Time
- O(n log n * L + m * log n * L)
- Space
- O(n) excluding output
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.