'''
keys: Sort and Binary Search the Prefix
Solutions:
Similar: 
T:
S:
'''
from typing import List
import bisect


class Solution:
    # advanced binary search version
    # T: O(nlogn), S: O(n)
    def suggestedProducts2(self, products: List[str], searchWord: str) -> List[List[str]]:
        products.sort()
        array_len = len(products)
        ans = []
        input_char = ""
        
        for char in searchWord:
            tmp = []
            input_char += char
            # find where input_char can be inserted in-order in the products array
            insertion_idx = self.binary_search(products, input_char)
            # check the following 3 words, if valid
            for word_idx in range(insertion_idx, min(array_len, insertion_idx+3)):
                if products[word_idx].startswith(input_char):
                    tmp.append(products[word_idx])
            ans.append(tmp)
        return ans
    
    def binary_search(self, array, target):
        # bisect.bisect_left implementation
        l = 0; r = len(array)
        while l < r:
            mid = l + (r - l) // 2
            if array[mid] < target:
                l = mid + 1
            else:
                r = mid
        return l
            

    
    # concise version
    # T: O(nlogn), S: O(n)
    def suggestedProducts1(self, A, word):
        A.sort()
        res, prefix, i = [], '', 0
        for c in word:
            prefix += c
            i = bisect.bisect_left(A, prefix, i)
            res.append([w for w in A[i:i + 3] if w.startswith(prefix)])
        return res
        
    # just some naive method
    def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:
        products.sort()
        res = []
        input_char = ""
        for char in searchWord:
            tmp = []
            input_char += char
            ct = 0
            for word in products:
                if word.startswith(input_char) and ct <= 2:
                    tmp.append(word)
                    ct += 1
            res.append(tmp)
        return res
            