Assignment: Predictive Text Assistant

Introduction:

Typing efficiently is essential in today's fast$-$paced digital world. Many devices offer predictive text assistance, suggesting letters or words to help users type faster. However, these predictions are not always accurate, leading to frustration and errors.

Imagine you are developing a personalized text suggestion system that predicts the most likely next letter$($s$)$ based on your typing history. This system analyzes past usage to provide tailored suggestions, reducing errors and improving the overall typing experience. Unlike existing systems, which complete entire words, your system focuses on suggesting only the most probable next letter$($s$),$ ensuring better flexibility and precision.

This program will simulate a text prediction engine capable of learning from user input and responding to queries with suggestions. It offers the following functionalities:

$1.$ Adding words and their usage frequencies to the system's dictionary.

$2.$ Respond to queries by predicting the most likely next letter based on the provided prefix. The program will appropriately inform the user if no words match a given prefix.

Example:

Suppose your dictionary contains the following data:

$-$ "hello" used $50$ times

$-$ "help" used $30$ times

$-$ "heat" used $20$ times

$-$ "hero" used $10$ times

If you query with the prefix, $"$he$",$ the system will analyze the words starting with $"$he$"$ and suggest the most likely next letter$($s$)$:

$-\text{'}1\text{'}$ appears in "hello" and "help" a total of $\backslash (50+30=80\backslash )$ times.

$-\text{'}$a$\text{'}$ appears in "heat" a total of $20$ times.

$-\text{'}$r$\text{'}$ appears in "hero" a total of $10$ times.

Thus, the most likely next letter is $1.$

If you query with the prefix ho$,$ since no word starts with ho$,$ the program will respond appropriately, indicating that no matching prefix exists in the dictionary.

The Problem

You are tasked with designing a system that answers queries about the most likely next letter based on a list of words and their usage frequencies. Your program will process a series of operations, which include adding words to a dictionary and querying for prefixes.

For each query, your program must:

$1.$ Return the most likely next letter$($s$)$ for the given prefix, based on the frequencies of words in the dictionary.

$2.$ If no word in the dictionary has the given prefix as a proper prefix $($i$.$e$.,$ the prefix is not strictly shorter than any matching word$),$ respond with "unrecognized prefix". The Input $($to be read from standard console input $($not file i$/0.$ Any file i$/$o in the code will get zero$))$

The input begins with a single positive integer, $\backslash (\backslash$boldsymbol$\{$n$\}\backslash ),$ which specifies the number of commands your program needs to process. Each of the following $\backslash (\backslash$boldsymbol$\{$n$\}\backslash )$ lines contains one command, in one of two formats:

$-$ Insert Command

A command that starts with the integer $1,$ followed by a word and a frequency:

$1$ sf

$-\backslash ($ s $\backslash )$ is a string of lowercase letters representing the word to be added to the dictionary.

$-\backslash ($ f $\backslash )$ is a positive integer representing the frequency with which the word was used. This command indicates that the word $\backslash ($ s $\backslash )$ has been used an additional ftimes $.$ Note that the same word may appear multiple times in the input, as users can use the same word at different times. The total usage frequency is the cumulative sum of all occurrences of the word.

$-$ Query

Command

A command that starts with the integer $2,$ followed by a prefix:

$2$ p

$-$ p is a string of lowercase letters representing the prefix for which the user wants a prediction.

This query asks the program to find the most likely next letter$($s$)$ based on the current dictionary. A query does not modify the dictionary.

More input specification:

$-$ The total number of letters in all input words will not exceed $\backslash (2,000,000\backslash ).$

$-$ The sum of the frequencies of all added words will not exceed $\backslash (1,000,000,000\backslash ).$

The Output $($to be printed to standard console output $($no file i$/$o$.$ Any file i$/$o in the code will get zero$))$

For each query command, your program must produce exactly one line of output:

$1.$ If the prefix is a proper prefix for one or more words in the dictionary at the time of the query:

$-$ Print all the letters that are the most likely to come next, in alphabetical order, without space between them.

$2.$ If the prefix is not a proper prefix for any word in the dictionary:

$-$ Print the string "unrecognized prefix" on a line by itself.

Implementation Restrictions

You are required to implement a trie data structure to manage all input words and handle queries. Each trie node should include the following information:

$1.$ Node Frequency: The frequency of the string represented by this node $($i$.$e$.,$ how many times this specific string has been added to the dictionary$).$

$2.$ Sum Prefix Frequency: The total frequency of all words in the dictionary that have this string as a prefix, including the string itself.

$3.$ Maximum Child Frequency: The highest frequency among all child nodes of the current node. For example, if the node represents "app" and there are currently $25$ occurrences of words starting with "appl" and $20$ with "appy," this value should be $25.$

$4.$ Children Pointe