Solution: Search Suggestions System
Tags: algorithms, javascript, java, python
Published: 2021-05-31 11:49:34

*This is part of a series of Leetcode solution explanations ([index](https://dev.to/seanpgallivan/leetcode-solutions-index-57fl)). If you liked this solution or found it useful,* ***please like*** *this post and/or* ***upvote*** *[my solution post on Leetcode's forums](https://leetcode.com/problems/search-suggestions-system/discuss/1242832).*

---

#### [Leetcode Problem #1268 (*Medium*): Search Suggestions System](https://leetcode.com/problems/search-suggestions-system/)

---

#### ***Description:***

<br />(*Jump to*: [*Solution Idea*](#idea) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

>
Given an array of strings `products` and a string `searchWord`. We want to design a system that suggests at most three product names from `products` after each character of `searchWord` is typed. Suggested products should have common prefix with the `searchWord`. If there are more than three products with a common prefix return the three lexicographically minimums products.
>
Return _list of lists_ of the suggested `products` after each character of `searchWord` is typed.

---

#### ***Examples:***
>
Example 1:||
|---:|---|
Input:| products = ["mobile","mouse","moneypot","monitor","mousepad"], searchWord = "mouse"
Output:| [<br>["mobile","moneypot","monitor"],<br>["mobile","moneypot","monitor"],<br>["mouse","mousepad"],<br>["mouse","mousepad"],<br>["mouse","mousepad"]<br>]
Explanation:| products sorted lexicographically = ["mobile","moneypot","monitor","mouse","mousepad"]<br>After typing m and mo all products match and we show user ["mobile","moneypot","monitor"]<br>After typing mou, mous and mouse the system suggests ["mouse","mousepad"]
>
Example 2:||
|---:|---|
Input:| products = ["havana"], searchWord = "havana"
Output:| [["havana"],["havana"],["havana"],["havana"],["havana"],["havana"]]
>
Example 3:||
|---:|---|
Input:| products = ["bags","baggage","banner","box","cloths"], searchWord = "bags"
Output:| [["baggage","bags","banner"],["baggage","bags","banner"],["baggage","bags"],["bags"]]
>
Example 4:||
|---:|---|
Input:| products = ["havana"], searchWord = "tatiana"
Output:| [[],[],[],[],[],[],[]]

---

#### ***Constraints:***
>
 - `1 <= products.length <= 1000`
 - There are no repeated elements in `products`.
 - `1 <= Σ products[i].length <= 2 * 10^4`
 - All characters of `products[i]` are lower-case English letters.
 - `1 <= searchWord.length <= 1000`
 - All characters of `searchWord` are lower-case English letters.

---

#### ***Idea:***

<br />(*Jump to*: [*Problem Description*](#description) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

Despite the fact that the clues suggest a **binary search** and a **trie**, the optimal solution to this problem needs neither. The substrings formed by adding one letter at a time from the search word (**S**) are naturally already in lexicographical order, as are the results that we're instructed to push into our answer array (**ans**).

So if we sort the products array (**P**), we should only ever need to iterate through **P** once during the entire remaining process of the solution with a **time complexity** of **O(N)**. A single binary search would only require **log(N) time**, but we'd have to perform **M = S.length** binary searches, so in total they would take **O(M * log(N)) time**, compared to the **O(N)** time of a simple iteration.

With constraints of **1000** on both **M** and **N**, the binary search route would max out at a worse time complexity than iteration. Regardless, the sort itself, which is required for both, requires **O(N * log(N))** time already, so neither option can decrease the overall time complexity required.

So in order to only require a single pass through **P**, we should keep track of the current bounds for the range of matches (**left, right**), then we'll iterate through the characters (**c**) of **S**. At each iteration, we'll first want to move **left** forward and **right** back to narrow the range of matches based on the new value of **c**.

Then we can add the next three elements of **P** to our result array (**res**), as long as they fall inside the range **[left, right]**. Once that's done, we can add **res** to **ans** and move to the next iteration.

Once we've finished iterating through **S**, we can **return ans**.

 - _**Time Complexity: O(N * log(N))** where **N** is the length of **P**_
 - _**Space Complexity: O(1)** excluding output space required for **ans**_

---

#### ***Javascript Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```javascript
var suggestedProducts = function(P, S) {
    P.sort()
    let ans = [], left = 0, right = P.length - 1
    for (let i = 0; i < S.length; i++) {
        let c = S.charAt(i), res = []
        while (P[left]?.charAt(i) < c) left++
        while (P[right]?.charAt(i) > c) right--
        for (let j = 0; j < 3 && left + j <= right; j++)
            res.push(P[left+j])
        ans.push(res)
    }
    return ans
};
```

---

#### ***Python Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```python
class Solution:
    def suggestedProducts(self, P: List[str], S: str) -> List[List[str]]:
        P.sort()
        ans, left, right = [], 0, len(P) - 1
        for i in range(len(S)):
            c, res = S[i], []
            while left <= right and (len(P[left]) == i or P[left][i] < c): left += 1
            while left <= right and (len(P[right]) == i or P[right][i] > c): right -= 1
            for j in range(3):
                if left + j > right: break
                else: res.append(P[left+j])
            ans.append(res)
        return ans
```

---

#### ***Java Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```java
class Solution {
    public List<List<String>> suggestedProducts(String[] P, String S) {
        Arrays.sort(P);
        List<List<String>> ans = new ArrayList<>();
        int left = 0, right = P.length - 1;
        for (int i = 0; i < S.length(); i++) {
            List<String> res = new ArrayList<>();
            char c = S.charAt(i);
            while (left <= right && (P[left].length() == i || P[left].charAt(i) < c)) left++;
            while (left <= right && (P[right].length() == i || P[right].charAt(i) > c)) right--;
            for (int j = 0; j < 3 && left + j <= right; j++)
                res.add(P[left+j]);
            ans.add(res);
        }
        return ans;
    }
}
```

---

#### ***C++ Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```c++
class Solution {
public:
    vector<vector<string>> suggestedProducts(vector<string>& P, string S) {
        sort(P.begin(), P.end());
        vector<vector<string>> ans;
        int left = 0, right = P.size() - 1;
        for (int i = 0; i < S.length(); i++) {
            vector<string> res;
            char c = S[i];
            while (left <= right && (P[left].length() == i || P[left][i] < c)) left++;
            while (left <= right && (P[right].length() == i || P[right][i] > c)) right--;
            for (int j = 0; j < 3 && left + j <= right; j++)
                res.push_back(P[left+j]);
            ans.push_back(res);
        }
        return ans;
    }
};
```