Search Suggestions System

Core idea: As a shopper types a search box character by character, you must show up to 3 product suggestions after every keystroke — the lexicographically smallest products that share the prefix typed so far. The unlocking move is to sort the products once. Once sorted, every word that starts with a given prefix forms a contiguous block. So for each growing prefix you just binary-search for where that block begins and grab the next ≤3 entries that still match — a tiny window that shrinks as the prefix grows. That's the crisp interview answer: O(n log n) to sort, then O(L log n) to answer all prefixes of a length-L query. The trie alternative (this is a Trie lesson, after all) caches the top-3 smallest words at every node, so each keystroke is a one-step walk — worth it when you answer many queries against one product set.

The problem, rephrased

You run the search bar for an online store. You're given a list of products (strings) and a searchWord the customer is about to type, one letter at a time. After each character they type, your autocomplete dropdown must show at most 3 product names that begin with everything typed so far. When more than 3 products qualify, show the 3 lexicographically smallest. Return a list of lists: one suggestion list per keystroke.

"Lexicographic" is just dictionary order — "mobile" comes before "mouse" because at the second character 'o' < 'o'... they tie, so on to the third: 'b' < 'u'. A prefix means starts with: typing "mo" matches "mobile" and "mouse" but not "banner".

This is LeetCode 1268 — Search Suggestions System.

The function returns one list per typed character (so a length-L searchWord yields exactly L lists).