Typeahead Top Three
MediumTries & Strings
Problem
A shop's search box suggests products as the customer types query one letter at a time. After each typed letter, it shows up to three product names that start with the text typed so far, choosing the lexicographically smallest ones.
Given the distinct names products and the query, return a list with one entry per typed letter: the suggestions in lexicographic order (possibly empty).
Example 1
- Input:
- products = ["banjo","banana","band","bandit","bank","bat"], query = "bat"
- Output:
- [["banana","band","bandit"],["banana","band","bandit"],["bat"]]
After "b" and "ba" all six match and the three smallest are shown; after "bat" only "bat" matches.
Example 2
- Input:
- products = ["tea"], query = "tex"
- Output:
- [["tea"],["tea"],[]]
Once the typed text matches nothing, every later list is empty.
Constraints
- 1 ≤ products.length ≤ 1000
- 1 ≤ products[i].length ≤ 3000
- Sum of product lengths ≤ 2·10^4
- 1 ≤ query.length ≤ 1000
- Lowercase English letters; product names are distinct.
Hint
Show the first hint
Each typed letter narrows the candidates to those sharing a longer prefix.
Walkthrough
How to approach it
01Clarify before coding
- Which three when more match? The lexicographically smallest.
- Are product names distinct? Yes.
- What after the query stops matching? Empty lists for that letter and every later one.
02Brute force
For every prefix of the query, filter all products by startsWith, sort, and take three.
Cost: O(|q| · (P·L + P log P)): repeated filtering and sorting for up to 1000 prefixes.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.