Search Suggestions System

How it works

Instead of binary searching for each prefix, we maintain a window [l, r] of valid products. As we process each character of the search word, we shrink the window by moving l forward past products that do not match at position i, and moving r backward past products that do not match. The first up to 3 products in the remaining window are our suggestions.

Steps

1. Sort the products array lexicographically.
2. Initialize two pointers l = 0 and r = n - 1.
3. For each index i from 0 to m - 1 (each character in searchWord):
   • Move l forward while products[l] is too short or has the wrong character at position i.
   • Move r backward while products[r] is too short or has the wrong character at position i.
   • Collect up to 3 products from the range [l, r].
   • Append the collected products to the result.
4. Return the result list.

Complexity

• Time complexity: O(n log n + m * w + N)
• Space complexity:
  • O(n) or O(1) space for the sorting algorithm.
  • O(m * w) space for the output array.

Where n is the total number of characters in the string array products, N is the size of the array products, m is the length of the string searchWord, and w is the average length of each word in the given string array.

Things to watch for

Forgetting to Sort Products First

The problem requires returning suggestions in lexicographical order. A common mistake is attempting to find matches without first sorting the products array. Without sorting, you cannot guarantee that the first three matching products are the lexicographically smallest ones.

Not Handling Short Products Correctly

When checking if a product matches the current prefix, you must verify that the product is long enough to contain the prefix. Accessing product[i] when product.length <= i causes an index out of bounds error. Always check the product length before comparing characters at a given position.

Inefficient Prefix Matching

Rebuilding or recomputing the prefix string from scratch for each character of the search word leads to unnecessary overhead. Instead, incrementally build the prefix by appending one character at a time, and reuse the previous search position since matching products form a contiguous block in the sorted array.

from typing import List

class Solution:
    def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:
        res = []
        products.sort()

        l, r = 0, len(products) - 1
        for i in range(len(searchWord)):
            c = searchWord[i]

            while l <= r and (len(products[l]) <= i or products[l][i] != c):
                l += 1
            while l <= r and (len(products[r]) <= i or products[r][i] != c):
                r -= 1

            res.append([])
            remain = r - l + 1
            for j in range(min(3, remain)):
                res[-1].append(products[l + j])

        return res

class Solution {
public:
    vector<vector<string>> suggestedProducts(vector<string>& products, string searchWord) {
        vector<vector<string>> res;
        sort(products.begin(), products.end());

        int l = 0, r = products.size() - 1;
        for (int i = 0; i < searchWord.size(); i++) {
            char c = searchWord[i];

            while (l <= r && (products[l].size() <= i || products[l][i] != c)) {
                l++;
            }
            while (l <= r && (products[r].size() <= i || products[r][i] != c)) {
                r--;
            }

            vector<string> cur;
            int remain = r - l + 1;
            for (int j = 0; j < min(3, remain); j++) {
                cur.push_back(products[l + j]);
            }

            res.push_back(cur);
        }

        return res;
    }
};