Company: Meesho
Difficulty: medium
Product Suggestions System For an array of n strings 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 the products array. The suggested products should share a common prefix with the searched word. If more than three products exist with a common prefix, report the three product names that appear first in lexicographical order. Input Format STRING_ARRAY products: the list of products STRING search: a string to search Output Format Return a vector of vectors containing strings. For each prefix of the search string, return a maximum of three lexicographically smallest words with a common prefix. Constraints 1 ≤ n ≤ 1000 1 ≤ length of products[i] ≤ 500 1 ≤ sum(length of products[i]) ≤ 5×10 5 All the strings of products are unique products[i] consists of lowercase English letters only 1 ≤ length of search ≤ 1000 The searched text consists of lowercase English letters only Example 1 Input: produc