Given an array of strings called products and a word to search, design a system that, when each character of the searched word is typed, suggests at most three product names from products. Suggested products should share a common prefix with the searched word. If more than three products exist with a common prefix, return the three product names that appear first in lexicographical order.

Return the suggested products, which will be a list of lists after each character of searched word is typed.

Constraints:

• $1 \leq$ products.length $\leq 1000$
• $1 \leq$ products[i].length $\leq 3000$
• $1 \leq$ sum(products[i].length) $\leq 2 \times 10^3$
• All the strings of products are unique.
• products[i] consists of lowercase English letters.
• $1 \leq$ searched word.length $\leq 1000$
• The searched word consists of lowercase English letters.

So far, you’ve probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which one to follow based on considerations such as time complexity and any implementation constraints.

A naive approach would be to first sort the given product data in lexicographic order to help with retrieving three matching products. Next, we iterate each character of the searched word, adding the current character to the substring to search for. We’ll search in the list of product names to check whether the current substring exists or not. If it exists, we’ll store the results (containing matching product names) for the current substring. We’ll repeat this process until we have traversed the whole list of product names.

It takes $O$ ...