1/**
2 * Trie node implementation for storing sentences with their frequencies
3 */
4class Trie {
5    // Array to store child nodes (26 letters + 1 space character)
6    Trie[] children = new Trie[27];
7    // Frequency count of the sentence ending at this node
8    int frequency;
9    // The complete sentence stored at this node
10    String sentence = "";
11
12    /**
13     * Inserts a sentence into the trie with given frequency
14     * @param sentence the sentence to insert
15     * @param times the frequency/times to add for this sentence
16     */
17    void insert(String sentence, int times) {
18        Trie currentNode = this;
19      
20        // Traverse through each character in the sentence
21        for (char ch : sentence.toCharArray()) {
22            // Map character to index: space -> 26, 'a'-'z' -> 0-25
23            int index = ch == ' ' ? 26 : ch - 'a';
24          
25            // Create new node if path doesn't exist
26            if (currentNode.children[index] == null) {
27                currentNode.children[index] = new Trie();
28            }
29            currentNode = currentNode.children[index];
30        }
31      
32        // Update frequency and store sentence at leaf node
33        currentNode.frequency += times;
34        currentNode.sentence = sentence;
35    }
36
37    /**
38     * Searches for a node with given prefix
39     * @param prefix the prefix to search for
40     * @return the trie node at the end of prefix path, or null if not found
41     */
42    Trie search(String prefix) {
43        Trie currentNode = this;
44      
45        // Traverse the trie following the prefix path
46        for (char ch : prefix.toCharArray()) {
47            // Map character to index: space -> 26, 'a'-'z' -> 0-25
48            int index = ch == ' ' ? 26 : ch - 'a';
49          
50            // Return null if prefix path doesn't exist
51            if (currentNode.children[index] == null) {
52                return null;
53            }
54            currentNode = currentNode.children[index];
55        }
56      
57        return currentNode;
58    }
59}
60
61/**
62 * Autocomplete system that suggests top 3 sentences based on user input
63 */
64class AutocompleteSystem {
65    // Root of the trie storing all sentences
66    private Trie trieRoot = new Trie();
67    // Buffer to store current user input
68    private StringBuilder currentInput = new StringBuilder();
69
70    /**
71     * Constructor to initialize the autocomplete system
72     * @param sentences array of initial sentences
73     * @param times array of frequencies corresponding to each sentence
74     */
75    public AutocompleteSystem(String[] sentences, int[] times) {
76        // Insert all initial sentences with their frequencies into the trie
77        int index = 0;
78        for (String sentence : sentences) {
79            trieRoot.insert(sentence, times[index++]);
80        }
81    }
82
83    /**
84     * Processes user input character and returns autocomplete suggestions
85     * @param c the input character
86     * @return list of top 3 autocomplete suggestions, or empty list if c is '#'
87     */
88    public List<String> input(char c) {
89        List<String> suggestions = new ArrayList<>();
90      
91        // Handle end of sentence input
92        if (c == '#') {
93            // Add the completed sentence to the trie with frequency 1
94            trieRoot.insert(currentInput.toString(), 1);
95            // Reset the input buffer for next sentence
96            currentInput = new StringBuilder();
97            return suggestions;
98        }
99      
100        // Append character to current input
101        currentInput.append(c);
102      
103        // Search for the prefix in the trie
104        Trie prefixNode = trieRoot.search(currentInput.toString());
105        if (prefixNode == null) {
106            return suggestions;
107        }
108      
109        // Use min heap to maintain top 3 sentences
110        // Priority: lower frequency first, then reverse alphabetical order
111        PriorityQueue<Trie> minHeap = new PriorityQueue<>((a, b) -> 
112            a.frequency == b.frequency ? b.sentence.compareTo(a.sentence) : a.frequency - b.frequency);
113      
114        // Find all sentences with the current prefix
115        dfs(prefixNode, minHeap);
116      
117        // Extract results from heap in reverse order
118        while (!minHeap.isEmpty()) {
119            suggestions.add(0, minHeap.poll().sentence);
120        }
121      
122        return suggestions;
123    }
124
125    /**
126     * Depth-first search to find all sentences in the subtree
127     * Maintains only top 3 sentences in the priority queue
128     * @param node current trie node
129     * @param minHeap priority queue to store top 3 sentences
130     */
131    private void dfs(Trie node, PriorityQueue<Trie> minHeap) {
132        if (node == null) {
133            return;
134        }
135      
136        // If this node represents a complete sentence
137        if (node.frequency > 0) {
138            minHeap.offer(node);
139            // Keep only top 3 sentences
140            if (minHeap.size() > 3) {
141                minHeap.poll();
142            }
143        }
144      
145        // Recursively search all children
146        for (Trie child : node.children) {
147            dfs(child, minHeap);
148        }
149    }
150}
151
152/**
153 * Your AutocompleteSystem object will be instantiated and called as such:
154 * AutocompleteSystem obj = new AutocompleteSystem(sentences, times);
155 * List<String> param_1 = obj.input(c);
156 */
157

1#include <vector>
2#include <string>
3#include <queue>
4#include <algorithm>
5
6using namespace std;
7
8/**
9 * Trie node implementation for storing sentences with their frequencies
10 */
11class TrieNode {
12public:
13    // Array to store child nodes (26 letters + 1 space character)
14    TrieNode* children[27];
15    // Frequency count of the sentence ending at this node
16    int frequency;
17    // The complete sentence stored at this node
18    string sentence;
19  
20    /**
21     * Constructor to initialize the trie node
22     */
23    TrieNode() {
24        for (int i = 0; i < 27; i++) {
25            children[i] = nullptr;
26        }
27        frequency = 0;
28        sentence = "";
29    }
30  
31    /**
32     * Inserts a sentence into the trie with given frequency
33     * @param sentence the sentence to insert
34     * @param times the frequency/times to add for this sentence
35     */
36    void insert(const string& sentence, int times) {
37        TrieNode* currentNode = this;
38      
39        // Traverse through each character in the sentence
40        for (char ch : sentence) {
41            // Map character to index: space -> 26, 'a'-'z' -> 0-25
42            int index = (ch == ' ') ? 26 : (ch - 'a');
43          
44            // Create new node if path doesn't exist
45            if (currentNode->children[index] == nullptr) {
46                currentNode->children[index] = new TrieNode();
47            }
48            currentNode = currentNode->children[index];
49        }
50      
51        // Update frequency and store sentence at leaf node
52        currentNode->frequency += times;
53        currentNode->sentence = sentence;
54    }
55  
56    /**
57     * Searches for a node with given prefix
58     * @param prefix the prefix to search for
59     * @return the trie node at the end of prefix path, or nullptr if not found
60     */
61    TrieNode* search(const string& prefix) {
62        TrieNode* currentNode = this;
63      
64        // Traverse the trie following the prefix path
65        for (char ch : prefix) {
66            // Map character to index: space -> 26, 'a'-'z' -> 0-25
67            int index = (ch == ' ') ? 26 : (ch - 'a');
68          
69            // Return nullptr if prefix path doesn't exist
70            if (currentNode->children[index] == nullptr) {
71                return nullptr;
72            }
73            currentNode = currentNode->children[index];
74        }
75      
76        return currentNode;
77    }
78};
79
80/**
81 * Autocomplete system that suggests top 3 sentences based on user input
82 */
83class AutocompleteSystem {
84private:
85    // Root of the trie storing all sentences
86    TrieNode* trieRoot;
87    // Buffer to store current user input
88    string currentInput;
89  
90    /**
91     * Comparator for the priority queue
92     * Priority: lower frequency first, then reverse alphabetical order
93     */
94    struct TrieNodeComparator {
95        bool operator()(TrieNode* a, TrieNode* b) {
96            if (a->frequency == b->frequency) {
97                return a->sentence < b->sentence;  // Reverse alphabetical for min heap
98            }
99            return a->frequency > b->frequency;  // Lower frequency has higher priority for min heap
100        }
101    };
102  
103    /**
104     * Depth-first search to find all sentences in the subtree
105     * Maintains only top 3 sentences in the priority queue
106     * @param node current trie node
107     * @param minHeap priority queue to store top 3 sentences
108     */
109    void dfs(TrieNode* node, priority_queue<TrieNode*, vector<TrieNode*>, TrieNodeComparator>& minHeap) {
110        if (node == nullptr) {
111            return;
112        }
113      
114        // If this node represents a complete sentence
115        if (node->frequency > 0) {
116            minHeap.push(node);
117            // Keep only top 3 sentences
118            if (minHeap.size() > 3) {
119                minHeap.pop();
120            }
121        }
122      
123        // Recursively search all children
124        for (int i = 0; i < 27; i++) {
125            dfs(node->children[i], minHeap);
126        }
127    }
128  
129public:
130    /**
131     * Constructor to initialize the autocomplete system
132     * @param sentences array of initial sentences
133     * @param times array of frequencies corresponding to each sentence
134     */
135    AutocompleteSystem(vector<string>& sentences, vector<int>& times) {
136        trieRoot = new TrieNode();
137        currentInput = "";
138      
139        // Insert all initial sentences with their frequencies into the trie
140        for (int i = 0; i < sentences.size(); i++) {
141            trieRoot->insert(sentences[i], times[i]);
142        }
143    }
144  
145    /**
146     * Processes user input character and returns autocomplete suggestions
147     * @param c the input character
148     * @return list of top 3 autocomplete suggestions, or empty list if c is '#'
149     */
150    vector<string> input(char c) {
151        vector<string> suggestions;
152      
153        // Handle end of sentence input
154        if (c == '#') {
155            // Add the completed sentence to the trie with frequency 1
156            trieRoot->insert(currentInput, 1);
157            // Reset the input buffer for next sentence
158            currentInput = "";
159            return suggestions;
160        }
161      
162        // Append character to current input
163        currentInput += c;
164      
165        // Search for the prefix in the trie
166        TrieNode* prefixNode = trieRoot->search(currentInput);
167        if (prefixNode == nullptr) {
168            return suggestions;
169        }
170      
171        // Use min heap to maintain top 3 sentences
172        // Priority: lower frequency first, then reverse alphabetical order
173        priority_queue<TrieNode*, vector<TrieNode*>, TrieNodeComparator> minHeap;
174      
175        // Find all sentences with the current prefix
176        dfs(prefixNode, minHeap);
177      
178        // Extract results from heap in reverse order
179        while (!minHeap.empty()) {
180            suggestions.insert(suggestions.begin(), minHeap.top()->sentence);
181            minHeap.pop();
182        }
183      
184        return suggestions;
185    }
186};
187
188/**
189 * Your AutocompleteSystem object will be instantiated and called as such:
190 * AutocompleteSystem* obj = new AutocompleteSystem(sentences, times);
191 * vector<string> param_1 = obj->input(c);
192 */
193

1/**
2 * Trie node structure for storing sentences with their frequencies
3 */
4interface TrieNode {
5    // Array to store child nodes (26 letters + 1 space character)
6    children: (TrieNode | null)[];
7    // Frequency count of the sentence ending at this node
8    frequency: number;
9    // The complete sentence stored at this node
10    sentence: string;
11}
12
13/**
14 * Creates a new trie node
15 */
16function createTrieNode(): TrieNode {
17    return {
18        children: new Array(27).fill(null),
19        frequency: 0,
20        sentence: ""
21    };
22}
23
24/**
25 * Inserts a sentence into the trie with given frequency
26 * @param root - The root node of the trie
27 * @param sentence - The sentence to insert
28 * @param times - The frequency/times to add for this sentence
29 */
30function insertIntoTrie(root: TrieNode, sentence: string, times: number): void {
31    let currentNode = root;
32  
33    // Traverse through each character in the sentence
34    for (const char of sentence) {
35        // Map character to index: space -> 26, 'a'-'z' -> 0-25
36        const index = char === ' ' ? 26 : char.charCodeAt(0) - 'a'.charCodeAt(0);
37      
38        // Create new node if path doesn't exist
39        if (currentNode.children[index] === null) {
40            currentNode.children[index] = createTrieNode();
41        }
42        currentNode = currentNode.children[index]!;
43    }
44  
45    // Update frequency and store sentence at leaf node
46    currentNode.frequency += times;
47    currentNode.sentence = sentence;
48}
49
50/**
51 * Searches for a node with given prefix
52 * @param root - The root node of the trie
53 * @param prefix - The prefix to search for
54 * @returns The trie node at the end of prefix path, or null if not found
55 */
56function searchInTrie(root: TrieNode, prefix: string): TrieNode | null {
57    let currentNode = root;
58  
59    // Traverse the trie following the prefix path
60    for (const char of prefix) {
61        // Map character to index: space -> 26, 'a'-'z' -> 0-25
62        const index = char === ' ' ? 26 : char.charCodeAt(0) - 'a'.charCodeAt(0);
63      
64        // Return null if prefix path doesn't exist
65        if (currentNode.children[index] === null) {
66            return null;
67        }
68        currentNode = currentNode.children[index]!;
69    }
70  
71    return currentNode;
72}
73
74// Global variables for the autocomplete system
75let trieRoot: TrieNode;
76let currentInput: string;
77
78/**
79 * Initializes the autocomplete system
80 * @param sentences - Array of initial sentences
81 * @param times - Array of frequencies corresponding to each sentence
82 */
83function AutocompleteSystem(sentences: string[], times: number[]): void {
84    // Initialize the trie root and current input buffer
85    trieRoot = createTrieNode();
86    currentInput = "";
87  
88    // Insert all initial sentences with their frequencies into the trie
89    for (let i = 0; i < sentences.length; i++) {
90        insertIntoTrie(trieRoot, sentences[i], times[i]);
91    }
92}
93
94/**
95 * Depth-first search to find all sentences in the subtree
96 * Maintains only top 3 sentences in the array
97 * @param node - Current trie node
98 * @param topSentences - Array to store top sentences with their frequencies
99 */
100function dfsCollectSentences(node: TrieNode | null, topSentences: TrieNode[]): void {
101    if (node === null) {
102        return;
103    }
104  
105    // If this node represents a complete sentence
106    if (node.frequency > 0) {
107        topSentences.push(node);
108      
109        // Sort to maintain top 3 sentences
110        // Priority: higher frequency first, then alphabetical order
111        topSentences.sort((a, b) => {
112            if (a.frequency === b.frequency) {
113                return a.sentence.localeCompare(b.sentence);
114            }
115            return b.frequency - a.frequency;
116        });
117      
118        // Keep only top 3 sentences
119        if (topSentences.length > 3) {
120            topSentences.pop();
121        }
122    }
123  
124    // Recursively search all children
125    for (const child of node.children) {
126        dfsCollectSentences(child, topSentences);
127    }
128}
129
130/**
131 * Processes user input character and returns autocomplete suggestions
132 * @param c - The input character
133 * @returns List of top 3 autocomplete suggestions, or empty list if c is '#'
134 */
135function input(c: string): string[] {
136    const suggestions: string[] = [];
137  
138    // Handle end of sentence input
139    if (c === '#') {
140        // Add the completed sentence to the trie with frequency 1
141        insertIntoTrie(trieRoot, currentInput, 1);
142        // Reset the input buffer for next sentence
143        currentInput = "";
144        return suggestions;
145    }
146  
147    // Append character to current input
148    currentInput += c;
149  
150    // Search for the prefix in the trie
151    const prefixNode = searchInTrie(trieRoot, currentInput);
152    if (prefixNode === null) {
153        return suggestions;
154    }
155  
156    // Collect all sentences with the current prefix
157    const topSentences: TrieNode[] = [];
158    dfsCollectSentences(prefixNode, topSentences);
159  
160    // Extract sentences from the sorted array
161    for (const node of topSentences) {
162        suggestions.push(node.sentence);
163    }
164  
165    return suggestions;
166}
167