Problem Description

The Search Suggestions System problem requires you to build an autocomplete system that suggests up to three product names from a list of products after each character of a searchWord is typed. The suggestions must be products that start with the current prefix and must be sorted lexicographically. If there are more than three matching products, return only the first three in lex order. For each prefix of the searchWord (i.e., after typing each character), you return a list of up to three product suggestions.

Constraints:

• Each product in products is a string of lowercase English letters.
• The list products contains no duplicates.
• All suggestions for a prefix must be distinct and sorted lexicographically.
• For each prefix, return up to three suggestions.
• Do not reuse elements in the same suggestion list.

Thought Process

When first approaching this problem, one might consider checking every product for every prefix of the searchWord. For each character typed, filter the list of products to those that start with the current prefix and sort them to get the top three. However, this approach is inefficient for large lists, as it repeats much of the same work for each new character.

To optimize, we notice that:

• Sorting the product list once at the beginning allows us to always retrieve suggestions in lexicographical order without repeated sorting.
• As the prefix grows, the set of matching products can only shrink, which suggests we can narrow our search window as we process each character.
• Using binary search, we can quickly find where the prefix would fit in the sorted list, and then simply check the next three products for matches.
• Alternatively, a Trie data structure can efficiently store all prefixes, but for the size limits here, sorting and binary search is often simpler and fast enough.

Solution Approach

Here’s a step-by-step breakdown of the efficient solution:

1. Sort the product list:
   • Sort products lexicographically. This ensures that any prefix search will yield suggestions in the correct order.
2. Iterate through each prefix of searchWord:
   • Build the current prefix by adding one character at a time from searchWord.
3. For each prefix, find suggestions:
   • Use binary search to find the insertion point for the current prefix in products.
   • From this point, check up to the next three products to see if they start with the prefix.
   • If they do, add them to the suggestions list for this prefix.
4. Store the suggestions:
   • For each prefix, collect the up to three matching products in a list.
   • Return a list of suggestion lists, one for each prefix.

Why this works: By sorting once and using binary search, we minimize repeated work and always present the lexicographically smallest suggestions. This approach is efficient and easy to implement.

Example Walkthrough

Let's walk through an example:

Input:
products = ["mobile","mouse","moneypot","monitor","mousepad"]
searchWord = "mouse"

1. Sort products: ["mobile","moneypot","monitor","mouse","mousepad"]
2. Type 'm' (prefix = "m"):
   • All products start with 'm', so suggestions: ["mobile","moneypot","monitor"]
3. Type 'o' (prefix = "mo"):
   • All products still match: ["mobile","moneypot","monitor"]
4. Type 'u' (prefix = "mou"):
   • Only "mouse" and "mousepad" match: ["mouse","mousepad"]
5. Type 's' (prefix = "mous"):
   • Still "mouse" and "mousepad": ["mouse","mousepad"]
6. Type 'e' (prefix = "mouse"):
   • Still "mouse" and "mousepad": ["mouse","mousepad"]

Output:
[["mobile","moneypot","monitor"],["mobile","moneypot","monitor"],["mouse","mousepad"],["mouse","mousepad"],["mouse","mousepad"]]

Time and Space Complexity

Brute-force approach:

• For each prefix, scan all products, filter, sort, and pick three: O(N * L * log N), where N is the number of products, and L is the length of searchWord.
• Space: O(N) for storing products and results.

• Sort products once: O(N log N).
• For each prefix (L total), binary search: O(log N) per prefix.
• For each prefix, check up to 3 products: O(1) per prefix.
• Total: O(N log N + L log N).
• Space: O(N) for products, O(L * 3) for results.

The optimized approach is much more efficient, especially for large lists and long search words.

Code Implementation

from bisect import bisect_left

class Solution:
    def suggestedProducts(self, products, searchWord):
        products.sort()
        res = []
        prefix = ""
        for c in searchWord:
            prefix += c
            # Find leftmost index where prefix could be inserted
            i = bisect_left(products, prefix)
            suggestions = []
            # Check up to three products starting at index i
            for j in range(i, min(i+3, len(products))):
                if products[j].startswith(prefix):
                    suggestions.append(products[j])
                else:
                    break
            res.append(suggestions)
        return res
      

#include <vector>
#include <string>
#include <algorithm>

using namespace std;

class Solution {
public:
    vector<vector<string>> suggestedProducts(vector<string>& products, string searchWord) {
        sort(products.begin(), products.end());
        vector<vector<string>> res;
        string prefix = "";
        for (char c : searchWord) {
            prefix += c;
            auto it = lower_bound(products.begin(), products.end(), prefix);
            vector<string> suggestions;
            for (int i = 0; i < 3 && it + i != products.end(); ++i) {
                if ((it + i)->substr(0, prefix.size()) == prefix)
                    suggestions.push_back(*(it + i));
                else
                    break;
            }
            res.push_back(suggestions);
        }
        return res;
    }
};
      

import java.util.*;

class Solution {
    public List<List<String>> suggestedProducts(String[] products, String searchWord) {
        Arrays.sort(products);
        List<List<String>> res = new ArrayList<>();
        String prefix = "";
        for (char c : searchWord.toCharArray()) {
            prefix += c;
            int i = Arrays.binarySearch(products, prefix);
            if (i < 0) i = -(i + 1);
            List<String> suggestions = new ArrayList<>();
            for (int j = i; j < Math.min(i + 3, products.length); ++j) {
                if (products[j].startsWith(prefix)) {
                    suggestions.add(products[j]);
                } else {
                    break;
                }
            }
            res.add(suggestions);
        }
        return res;
    }
}
      

/**
 * @param {string[]} products
 * @param {string} searchWord
 * @return {string[][]}
 */
var suggestedProducts = function(products, searchWord) {
    products.sort();
    let res = [];
    let prefix = "";
    for (let i = 0; i < searchWord.length; ++i) {
        prefix += searchWord[i];
        // Binary search to find leftmost index
        let l = 0, r = products.length;
        while (l < r) {
            let m = Math.floor((l + r) / 2);
            if (products[m] < prefix) l = m + 1;
            else r = m;
        }
        let suggestions = [];
        for (let j = l; j < Math.min(l + 3, products.length); ++j) {
            if (products[j].startsWith(prefix)) {
                suggestions.push(products[j]);
            } else {
                break;
            }
        }
        res.push(suggestions);
    }
    return res;
};
      

Summary

The Search Suggestions System problem is elegantly solved by sorting the product list and using binary search to efficiently find suggestions for each prefix of the search word. This approach avoids redundant work, guarantees lexicographical order, and is simple to implement. The key insight is that as the prefix grows, the set of matching products only shrinks, allowing us to efficiently narrow our search and always provide the best possible suggestions.