1268. Search Suggestions System - Explanation

Description

After each character of searchWord is typed, suggest up to three names from products that begin with the entire prefix typed so far.

Choose the matching names that come first in lexicographical order, and list them in that order. Return one list for every typed character, including empty lists when no product matches. Product names are unique and contain only lowercase English letters.

Example 1:

Input: products = ["cat","camera","car","dog"]
searchWord = "cat"

Output: [["camera","car","cat"],["camera","car","cat"],["cat"]]

Explanation: After "c" and "ca", the matching names in lexicographical order are "camera", "car", and "cat". After "cat", only "cat" still matches.

Example 2:

Input: products = ["a","ab","abc"]
searchWord = "abcd"

Output: [["a","ab","abc"],["ab","abc"],["abc"],[]]

Explanation: Typing "a" matches all three products. Typing "ab" leaves "ab" and "abc", then typing "abc" leaves only "abc". No product begins with "abcd", so the last list is empty.

Example 3:

Input: products = ["zebra","apple"]
searchWord = "mo"

Output: [[],[]]

Explanation: No product starts with "m", so there are no suggestions after either "m" or "mo". Return an empty list for each character typed.

Constraints:

1 <= products.length <= 1000
1 <= products[i].length <= 3000
The sum of all product-name lengths is at most 20000.
All product names are unique.
1 <= searchWord.length <= 1000
All strings contain only lowercase English letters.

Topics

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

Sorting - Understanding how to sort strings lexicographically to enable efficient prefix matching
Binary Search - Using binary search to find the first element matching a prefix in a sorted array
String Manipulation - Working with prefixes and comparing strings character by character
Two Pointers - Maintaining a window of valid candidates that shrinks as the prefix grows

1. Brute Force

Intuition

For each prefix of the search word, we need to find up to three products that match that prefix in lexicographical order. By sorting products first, we guarantee that the first matching products we encounter are the lexicographically smallest. We then scan through all products for each prefix, collecting up to three matches.

Algorithm

Sort the products array lexicographically.
For each prefix length i from 1 to m (length of searchWord):
- Create an empty list for current suggestions.
- Iterate through all products and check if the first i characters match the current prefix.
- Add matching products to the list until we have 3.
- If no matches are found, fill remaining positions with empty lists and break early.
- Append the current suggestions to the result.
Return the result list.

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

        for i in range(m):
            cur = []
            for w in products:
                if len(w) <= i:
                    continue

                flag = True
                for j in range(i + 1):
                    if w[j] != searchWord[j]:
                        flag = False
                        break

                if flag:
                    cur.append(w)
                    if len(cur) == 3:
                        break

            if not cur:
                for j in range(i, m):
                    res.append([])
                break
            res.append(cur)

        return res

public class Solution {
    public List<List<String>> suggestedProducts(String[] products, String searchWord) {
        List<List<String>> res = new ArrayList<>();
        int m = searchWord.length();
        Arrays.sort(products);

        for (int i = 0; i < m; i++) {
            List<String> cur = new ArrayList<>();
            for (String w : products) {
                if (w.length() <= i) continue;

                boolean flag = true;
                for (int j = 0; j <= i; j++) {
                    if (w.charAt(j) != searchWord.charAt(j)) {
                        flag = false;
                        break;
                    }
                }

                if (flag) {
                    cur.add(w);
                    if (cur.size() == 3) break;
                }
            }

            if (cur.isEmpty()) {
                while (i < m) {
                    res.add(new ArrayList<>());
                    i++;
                }
                break;
            }

            res.add(cur);
        }

        return res;
    }
}

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

        for (int i = 0; i < m; i++) {
            vector<string> cur;
            for (const string& w : products) {
                if (w.size() <= i) continue;

                bool flag = true;
                for (int j = 0; j <= i; j++) {
                    if (w[j] != searchWord[j]) {
                        flag = false;
                        break;
                    }
                }

                if (flag) {
                    cur.push_back(w);
                    if (cur.size() == 3) break;
                }
            }

            if (cur.empty()) {
                while (i < m) {
                    res.push_back({});
                    i++;
                }
                break;
            }

            res.push_back(cur);
        }

        return res;
    }
};

class Solution {
    /**
     * @param {string[]} products
     * @param {string} searchWord
     * @return {string[][]}
     */
    suggestedProducts(products, searchWord) {
        let res = [];
        let m = searchWord.length;
        products.sort();

        for (let i = 0; i < m; i++) {
            let cur = [];
            for (let w of products) {
                if (w.length <= i) continue;

                let flag = true;
                for (let j = 0; j <= i; j++) {
                    if (w[j] !== searchWord[j]) {
                        flag = false;
                        break;
                    }
                }

                if (flag) {
                    cur.push(w);
                    if (cur.length === 3) break;
                }
            }

            if (cur.length === 0) {
                while (i < m) {
                    res.push([]);
                    i++;
                }
                break;
            }

            res.push(cur);
        }

        return res;
    }
}

public class Solution {
    public IList<IList<string>> SuggestedProducts(string[] products, string searchWord) {
        var res = new List<IList<string>>();
        int m = searchWord.Length;
        Array.Sort(products);

        for (int i = 0; i < m; i++) {
            var cur = new List<string>();
            foreach (var w in products) {
                if (w.Length <= i) continue;

                bool flag = true;
                for (int j = 0; j <= i; j++) {
                    if (w[j] != searchWord[j]) {
                        flag = false;
                        break;
                    }
                }

                if (flag) {
                    cur.Add(w);
                    if (cur.Count == 3) break;
                }
            }

            if (cur.Count == 0) {
                while (i < m) {
                    res.Add(new List<string>());
                    i++;
                }
                break;
            }

            res.Add(cur);
        }

        return res;
    }
}

import "sort"

func suggestedProducts(products []string, searchWord string) [][]string {
    res := [][]string{}
    m := len(searchWord)
    sort.Strings(products)

    for i := 0; i < m; i++ {
        cur := []string{}
        for _, w := range products {
            if len(w) <= i {
                continue
            }

            flag := true
            for j := 0; j <= i; j++ {
                if w[j] != searchWord[j] {
                    flag = false
                    break
                }
            }

            if flag {
                cur = append(cur, w)
                if len(cur) == 3 {
                    break
                }
            }
        }

        if len(cur) == 0 {
            for i < m {
                res = append(res, []string{})
                i++
            }
            break
        }

        res = append(res, cur)
    }

    return res
}

class Solution {
    fun suggestedProducts(products: Array<String>, searchWord: String): List<List<String>> {
        val res = mutableListOf<List<String>>()
        val m = searchWord.length
        products.sort()

        var i = 0
        while (i < m) {
            val cur = mutableListOf<String>()
            for (w in products) {
                if (w.length <= i) continue

                var flag = true
                for (j in 0..i) {
                    if (w[j] != searchWord[j]) {
                        flag = false
                        break
                    }
                }

                if (flag) {
                    cur.add(w)
                    if (cur.size == 3) break
                }
            }

            if (cur.isEmpty()) {
                while (i < m) {
                    res.add(emptyList())
                    i++
                }
                break
            }

            res.add(cur)
            i++
        }

        return res
    }
}

class Solution {
    func suggestedProducts(_ products: [String], _ searchWord: String) -> [[String]] {
        var res = [[String]]()
        let m = searchWord.count
        let sortedProducts = products.sorted()
        let searchArray = Array(searchWord)

        var i = 0
        while i < m {
            var cur = [String]()
            for w in sortedProducts {
                let wArray = Array(w)
                if wArray.count <= i { continue }

                var flag = true
                for j in 0...i {
                    if wArray[j] != searchArray[j] {
                        flag = false
                        break
                    }
                }

                if flag {
                    cur.append(w)
                    if cur.count == 3 { break }
                }
            }

            if cur.isEmpty {
                while i < m {
                    res.append([])
                    i += 1
                }
                break
            }

            res.append(cur)
            i += 1
        }

        return res
    }
}

impl Solution {
    pub fn suggested_products(products: Vec<String>, search_word: String) -> Vec<Vec<String>> {
        let mut res = Vec::new();
        let m = search_word.len();
        let search_bytes = search_word.as_bytes();
        let mut products = products;
        products.sort();

        let mut i = 0;
        while i < m {
            let mut cur = Vec::new();
            for w in &products {
                let wb = w.as_bytes();
                if wb.len() <= i {
                    continue;
                }
                let mut flag = true;
                for j in 0..=i {
                    if wb[j] != search_bytes[j] {
                        flag = false;
                        break;
                    }
                }
                if flag {
                    cur.push(w.clone());
                    if cur.len() == 3 {
                        break;
                    }
                }
            }
            if cur.is_empty() {
                while i < m {
                    res.push(vec![]);
                    i += 1;
                }
                break;
            }
            res.push(cur);
            i += 1;
        }

        res
    }
}

Time & Space Complexity

Time complexity: $O(n \log n + m * 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$ , $m$ is the length of the string $searchWord$ , and $w$ is the average length of each word in the given string array.

2. Sorting + Binary Search

Intuition

Once products are sorted, all products sharing a prefix form a contiguous block. Instead of scanning all products for each prefix, we use binary search to find where this block starts. Since the prefix grows character by character, the start position can only move forward, so we keep track of it across iterations.

Algorithm

Sort the products array lexicographically.
Initialize prefix as an empty string and start = 0.
For each character in searchWord:
- Append the character to prefix.
- Use binary search to find the first product >= prefix, starting from start.
- Update start to this position.
- Collect up to 3 products starting from start that have prefix as their prefix.
- Append the collected products to the result.
Return the result list.

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

        prefix = []
        start = 0

        def binary_search(target, start):
            l, r = start, len(products)
            while l < r:
                mid = l + (r - l) // 2
                if products[mid] >= target:
                    r = mid
                else:
                    l = mid + 1
            return l

        for i in range(m):
            prefix.append(searchWord[i])
            start = binary_search("".join(prefix), start)

            cur = []
            for j in range(start, min(start + 3, len(products))):
                if products[j].startswith("".join(prefix)):
                    cur.append(products[j])
                else:
                    break

            res.append(cur)

        return res

public class Solution {
    public List<List<String>> suggestedProducts(String[] products, String searchWord) {
        List<List<String>> res = new ArrayList<>();
        int m = searchWord.length();
        Arrays.sort(products);

        StringBuilder prefix = new StringBuilder();
        int start = 0;

        for (int i = 0; i < m; i++) {
            prefix.append(searchWord.charAt(i));
            start = binarySearch(products, prefix.toString(), start);

            List<String> cur = new ArrayList<>();
            for (int j = start; j < Math.min(start + 3, products.length); j++) {
                if (products[j].startsWith(prefix.toString())) {
                    cur.add(products[j]);
                } else {
                    break;
                }
            }

            res.add(cur);
        }

        return res;
    }

    private int binarySearch(String[] products, String target, int start) {
        int l = start, r = products.length;
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (products[mid].compareTo(target) >= 0) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }
}

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

        string prefix = "";
        int start = 0;

        for (int i = 0; i < m; i++) {
            prefix += searchWord[i];
            start = binarySearch(products, prefix, start);

            vector<string> cur;
            for (int j = start; j < min(start + 3, (int)products.size()); j++) {
                if (products[j].substr(0, prefix.size()) == prefix) {
                    cur.push_back(products[j]);
                } else {
                    break;
                }
            }

            res.push_back(cur);
        }

        return res;
    }

private:
    int binarySearch(vector<string>& products, string target, int start) {
        int l = start, r = products.size();
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (products[mid] >= target) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }
};

class Solution {
    /**
     * @param {string[]} products
     * @param {string} searchWord
     * @return {string[][]}
     */
    suggestedProducts(products, searchWord) {
        let res = [];
        let m = searchWord.length;
        products.sort();

        let prefix = [];
        let start = 0;

        for (let i = 0; i < m; i++) {
            prefix.push(searchWord[i]);
            start = this.binarySearch(products, prefix.join(''), start);

            let cur = [];
            for (let j = start; j < Math.min(start + 3, products.length); j++) {
                if (products[j].startsWith(prefix.join(''))) {
                    cur.push(products[j]);
                } else {
                    break;
                }
            }

            res.push(cur);
        }

        return res;
    }

    /**
     * @param {string[]} products
     * @param {string} target
     * @param {number} start
     * @return {number}
     */
    binarySearch(products, target, start) {
        let l = start,
            r = products.length;
        while (l < r) {
            let mid = Math.floor(l + (r - l) / 2);
            if (products[mid] >= target) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }
}

public class Solution {
    public IList<IList<string>> SuggestedProducts(string[] products, string searchWord) {
        var res = new List<IList<string>>();
        int m = searchWord.Length;
        Array.Sort(products);

        var prefix = new System.Text.StringBuilder();
        int start = 0;

        for (int i = 0; i < m; i++) {
            prefix.Append(searchWord[i]);
            start = BinarySearch(products, prefix.ToString(), start);

            var cur = new List<string>();
            for (int j = start; j < Math.Min(start + 3, products.Length); j++) {
                if (products[j].StartsWith(prefix.ToString())) {
                    cur.Add(products[j]);
                } else {
                    break;
                }
            }

            res.Add(cur);
        }

        return res;
    }

    private int BinarySearch(string[] products, string target, int start) {
        int l = start, r = products.Length;
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (string.Compare(products[mid], target) >= 0) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }
}

import (
    "sort"
    "strings"
)

func suggestedProducts(products []string, searchWord string) [][]string {
    res := [][]string{}
    m := len(searchWord)
    sort.Strings(products)

    prefix := ""
    start := 0

    binarySearch := func(target string, start int) int {
        l, r := start, len(products)
        for l < r {
            mid := l + (r-l)/2
            if products[mid] >= target {
                r = mid
            } else {
                l = mid + 1
            }
        }
        return l
    }

    for i := 0; i < m; i++ {
        prefix += string(searchWord[i])
        start = binarySearch(prefix, start)

        cur := []string{}
        for j := start; j < min(start+3, len(products)); j++ {
            if strings.HasPrefix(products[j], prefix) {
                cur = append(cur, products[j])
            } else {
                break
            }
        }

        res = append(res, cur)
    }

    return res
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

class Solution {
    fun suggestedProducts(products: Array<String>, searchWord: String): List<List<String>> {
        val res = mutableListOf<List<String>>()
        val m = searchWord.length
        products.sort()

        val prefix = StringBuilder()
        var start = 0

        for (i in 0 until m) {
            prefix.append(searchWord[i])
            start = binarySearch(products, prefix.toString(), start)

            val cur = mutableListOf<String>()
            for (j in start until minOf(start + 3, products.size)) {
                if (products[j].startsWith(prefix.toString())) {
                    cur.add(products[j])
                } else {
                    break
                }
            }

            res.add(cur)
        }

        return res
    }

    private fun binarySearch(products: Array<String>, target: String, start: Int): Int {
        var l = start
        var r = products.size
        while (l < r) {
            val mid = l + (r - l) / 2
            if (products[mid] >= target) {
                r = mid
            } else {
                l = mid + 1
            }
        }
        return l
    }
}

class Solution {
    func suggestedProducts(_ products: [String], _ searchWord: String) -> [[String]] {
        var res = [[String]]()
        let m = searchWord.count
        let sortedProducts = products.sorted()
        let searchArray = Array(searchWord)

        var prefix = ""
        var start = 0

        func binarySearch(_ target: String, _ start: Int) -> Int {
            var l = start
            var r = sortedProducts.count
            while l < r {
                let mid = l + (r - l) / 2
                if sortedProducts[mid] >= target {
                    r = mid
                } else {
                    l = mid + 1
                }
            }
            return l
        }

        for i in 0..<m {
            prefix += String(searchArray[i])
            start = binarySearch(prefix, start)

            var cur = [String]()
            for j in start..<min(start + 3, sortedProducts.count) {
                if sortedProducts[j].hasPrefix(prefix) {
                    cur.append(sortedProducts[j])
                } else {
                    break
                }
            }

            res.append(cur)
        }

        return res
    }
}

impl Solution {
    pub fn suggested_products(products: Vec<String>, search_word: String) -> Vec<Vec<String>> {
        let mut products = products;
        products.sort();
        let mut res = Vec::new();
        let m = search_word.len();
        let mut prefix = String::new();
        let mut start = 0;

        let search_bytes = search_word.as_bytes();
        for i in 0..m {
            prefix.push(search_bytes[i] as char);
            let mut l = start;
            let mut r = products.len();
            while l < r {
                let mid = l + (r - l) / 2;
                if products[mid].as_str() >= prefix.as_str() {
                    r = mid;
                } else {
                    l = mid + 1;
                }
            }
            start = l;

            let mut cur = Vec::new();
            for j in start..products.len().min(start + 3) {
                if products[j].starts_with(&prefix) {
                    cur.push(products[j].clone());
                } else {
                    break;
                }
            }
            res.push(cur);
        }

        res
    }
}

Time & Space Complexity

Time complexity: $O(n \log n + m * w * \log 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.

3. Sorting + Binary Search (Built-In Function)

Intuition

This approach is identical to the previous one, but uses built-in binary search functions provided by the language. Functions like bisect_left in Python or lower_bound in C++ handle the binary search logic, making the code cleaner and less error-prone.

Algorithm

Sort the products array lexicographically.
Initialize prefix as an empty string and start = 0.
For each character in searchWord:
- Append the character to prefix.
- Use the built-in lower bound function to find the first product >= prefix.
- Collect up to 3 products from that position that have prefix as their prefix.
- Append the collected products to the result.
Return the result list.

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

        prefix = ""
        start = 0
        for i in range(m):
            prefix += searchWord[i]
            start = bisect_left(products, prefix, start)

            cur = []
            for j in range(start, min(start + 3, len(products))):
                if products[j].startswith(prefix):
                    cur.append(products[j])
                else:
                    break

            res.append(cur)

        return res

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

        string prefix = "";
        int start = 0;
        for (int i = 0; i < m; i++) {
            prefix += searchWord[i];
            start = lower_bound(products.begin() + start, products.end(), prefix) - products.begin();

            vector<string> cur;
            for (int j = start; j < min(start + 3, (int)products.size()); j++) {
                if (products[j].find(prefix) == 0) {
                    cur.push_back(products[j]);
                } else {
                    break;
                }
            }

            res.push_back(cur);
        }

        return res;
    }
};

import (
    "sort"
    "strings"
)

func suggestedProducts(products []string, searchWord string) [][]string {
    res := [][]string{}
    m := len(searchWord)
    sort.Strings(products)

    prefix := ""
    start := 0

    for i := 0; i < m; i++ {
        prefix += string(searchWord[i])
        start = sort.SearchStrings(products[start:], prefix) + start

        cur := []string{}
        for j := start; j < min(start+3, len(products)); j++ {
            if strings.HasPrefix(products[j], prefix) {
                cur = append(cur, products[j])
            } else {
                break
            }
        }

        res = append(res, cur)
    }

    return res
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

impl Solution {
    pub fn suggested_products(products: Vec<String>, search_word: String) -> Vec<Vec<String>> {
        let mut products = products;
        products.sort();
        let mut res = Vec::new();
        let mut prefix = String::new();
        let mut start = 0;

        for ch in search_word.chars() {
            prefix.push(ch);
            start += products[start..].partition_point(|p| p.as_str() < prefix.as_str());

            let mut cur = Vec::new();
            for j in start..products.len().min(start + 3) {
                if products[j].starts_with(&prefix) {
                    cur.push(products[j].clone());
                } else {
                    break;
                }
            }
            res.push(cur);
        }

        res
    }
}

Time & Space Complexity

Time complexity: $O(n \log n + m * w * \log 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.

4. Sorting + Two Pointers

Intuition

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.

Algorithm

Sort the products array lexicographically.
Initialize two pointers l = 0 and r = n - 1.
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.
Return the result 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

public class Solution {
    public List<List<String>> suggestedProducts(String[] products, String searchWord) {
        List<List<String>> res = new ArrayList<>();
        Arrays.sort(products);

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

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

            List<String> cur = new ArrayList<>();
            int remain = r - l + 1;
            for (int j = 0; j < Math.min(3, remain); j++) {
                cur.add(products[l + j]);
            }

            res.add(cur);
        }

        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;
    }
};

class Solution {
    /**
     * @param {string[]} products
     * @param {string} searchWord
     * @return {string[][]}
     */
    suggestedProducts(products, searchWord) {
        let res = [];
        products.sort();

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

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

            let cur = [];
            let remain = r - l + 1;
            for (let j = 0; j < Math.min(3, remain); j++) {
                cur.push(products[l + j]);
            }

            res.push(cur);
        }

        return res;
    }
}

public class Solution {
    public IList<IList<string>> SuggestedProducts(string[] products, string searchWord) {
        var res = new List<IList<string>>();
        Array.Sort(products);

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

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

            var cur = new List<string>();
            int remain = r - l + 1;
            for (int j = 0; j < Math.Min(3, remain); j++) {
                cur.Add(products[l + j]);
            }

            res.Add(cur);
        }

        return res;
    }
}

import "sort"

func suggestedProducts(products []string, searchWord string) [][]string {
    res := [][]string{}
    sort.Strings(products)

    l, r := 0, len(products)-1
    for i := 0; i < len(searchWord); i++ {
        c := searchWord[i]

        for l <= r && (len(products[l]) <= i || products[l][i] != c) {
            l++
        }
        for l <= r && (len(products[r]) <= i || products[r][i] != c) {
            r--
        }

        cur := []string{}
        remain := r - l + 1
        for j := 0; j < min(3, remain); j++ {
            cur = append(cur, products[l+j])
        }

        res = append(res, cur)
    }

    return res
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

class Solution {
    fun suggestedProducts(products: Array<String>, searchWord: String): List<List<String>> {
        val res = mutableListOf<List<String>>()
        products.sort()

        var l = 0
        var r = products.size - 1
        for (i in searchWord.indices) {
            val c = searchWord[i]

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

            val cur = mutableListOf<String>()
            val remain = r - l + 1
            for (j in 0 until minOf(3, remain)) {
                cur.add(products[l + j])
            }

            res.add(cur)
        }

        return res
    }
}

class Solution {
    func suggestedProducts(_ products: [String], _ searchWord: String) -> [[String]] {
        var res = [[String]]()
        let sortedProducts = products.sorted()
        let searchArray = Array(searchWord)

        var l = 0
        var r = sortedProducts.count - 1
        for i in 0..<searchArray.count {
            let c = searchArray[i]

            while l <= r {
                let lArray = Array(sortedProducts[l])
                if lArray.count <= i || lArray[i] != c {
                    l += 1
                } else {
                    break
                }
            }
            while l <= r {
                let rArray = Array(sortedProducts[r])
                if rArray.count <= i || rArray[i] != c {
                    r -= 1
                } else {
                    break
                }
            }

            var cur = [String]()
            let remain = r - l + 1
            for j in 0..<min(3, remain) {
                cur.append(sortedProducts[l + j])
            }

            res.append(cur)
        }

        return res
    }
}

impl Solution {
    pub fn suggested_products(products: Vec<String>, search_word: String) -> Vec<Vec<String>> {
        let mut products = products;
        products.sort();
        let mut res = Vec::new();
        let search_bytes = search_word.as_bytes();

        let mut l: i32 = 0;
        let mut r: i32 = products.len() as i32 - 1;
        for i in 0..search_bytes.len() {
            let c = search_bytes[i];

            while l <= r
                && (products[l as usize].len() <= i
                    || products[l as usize].as_bytes()[i] != c)
            {
                l += 1;
            }
            while l <= r
                && (products[r as usize].len() <= i
                    || products[r as usize].as_bytes()[i] != c)
            {
                r -= 1;
            }

            let mut cur = Vec::new();
            let remain = r - l + 1;
            for j in 0..3.min(remain) {
                cur.push(products[(l + j) as usize].clone());
            }
            res.push(cur);
        }

        res
    }
}

Time & Space 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.

Common Pitfalls

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.