Untitled

import java.util.*;

class Solution {
    public List<List<String>> suggestedProducts(String[] products, String searchWord) {
        Arrays.sort(products); // Step 1: Sort lexicographically
        List<List<String>> result = new ArrayList<>();
        String prefix = "";
        int startIndex = 0; // Start searching from here to optimize
        
        for (char c : searchWord.toCharArray()) {
            prefix += c;
            startIndex = lowerBound(products, prefix, startIndex); // Step 2: Find start of prefix
            List<String> suggestions = new ArrayList<>();
            
            for (int i = startIndex; i < Math.min(products.length, startIndex + 3); i++) {
                if (!products[i].startsWith(prefix)) break;
                suggestions.add(products[i]);
            }
            
            result.add(suggestions);
        }
        
        return result;
    }

    // Binary search to find the first index where prefix starts
    private int lowerBound(String[] products, String prefix, int start) {
        int left = start, right = products.length;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (products[mid].compareTo(prefix) >= 0) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}