def search_autocomplete_brute_force(search_terms, user_input):
    suggested_terms = []
    
    # Iterate through all possible extensions of the user's input
    for search_term in search_terms:
        if search_term.startswith(user_input):
            # Add the search term to suggested terms if it matches.
            suggested_terms.append(search_term)

    return suggested_terms

def search_autocomplete_with_ranking(
    search_terms,
    user_input,
    popularity_scores
):
    suggested_terms = search_autocomplete_brute_force(
        search_terms,
        user_input
    )

    # Filter for terms where popularity scores are known
    available_suggestions = [
        term for term in suggested_terms if term in popularity_scores
    ]

    # Sort by popularity. 
    ranked_suggestions = sorted(
        available_suggestions,
        key=lambda term: popularity_scores[term],
        reverse=True
    )
    
    # Only show the top 5 suggestions.
    return ranked_suggestions[:5]

class TrieNode:
    def __init__(self):
        self.children = {}
        self.suggestions = []

class AutocompleteSystem:
    def __init__(self, sentences, times):
        self.root = TrieNode()
        self.current_prefix = ""
        
        for i in range(len(sentences)):
            self.add_sentence(sentences[i], times[i])

    def add_sentence(self, sentence, hot):
        node = self.root
        for char in sentence:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
            node.suggestions.append((sentence, hot))
            node.suggestions.sort(key=lambda item: (-item[1], item[0]))
            if len(node.suggestions) > 3:
                node.suggestions.pop()

    def get_suggestions(self, prefix):
        node = self.root
        for char in prefix:
            if char not in node.children:
                return []
            node = node.children[char]
        
        return [item[0] for item in node.suggestions]

    def input(self, character):
        if character == '#':
            self.add_sentence(self.current_prefix, 1)
            self.current_prefix = ""
            return []

        self.current_prefix += character
        return self.get_suggestions(self.current_prefix)

# The Trie data structure is initialized.
# Each node represents a character in a potential search term.
def example_usage():
    sentences = ["i love you", "island", "iroman", "i love leetcode"]
    times = [5, 3, 2, 2]
    auto_complete_system = AutocompleteSystem(sentences, times)

    print(auto_complete_system.input('i'))
    print(auto_complete_system.input(' '))
    print(auto_complete_system.input('l'))
    print(auto_complete_system.input('o'))
    print(auto_complete_system.input('v'))
    print(auto_complete_system.input('e'))
    print(auto_complete_system.input(' '))
    print(auto_complete_system.input('y'))
    print(auto_complete_system.input('o'))
    print(auto_complete_system.input('u'))
    print(auto_complete_system.input('#'))

    print(auto_complete_system.input('i'))

# Adding a new sentence or incrementing the 'hot' score
# updates the Trie's suggestion lists based on popularity.

# Every typed character updates current_prefix, which then
# queries the trie and returns top suggestions.

# This function demonstrates the AutocompleteSystem in action
# It initializes the system, processes input, and prints the output.
if __name__ == '__main__':
    example_usage()