class AutocompleteSystem {
Map<String, Integer> count;
public TrieNode(char val) {
childNode = new TrieNode[27];
root = new TrieNode(' ');
public void insert(String sentence, int frequency) {
for (char c : sentence.toCharArray()) {
int index = c == ' ' ? 26 : c - 'a';
if (curNode.childNode[index] == null) {
curNode.childNode[index] = new TrieNode(c);
curNode = curNode.childNode[index];
curNode.count.put(sentence, curNode.count.getOrDefault(sentence, 0) + frequency);
public TrieNode search(String prefix) {
for (char c : prefix.toCharArray()) {
int index = c == ' ' ? 26 : c - 'a';
if (curNode.childNode[index] == null) {
curNode = curNode.childNode[index];
class WordInfo implements Comparable<WordInfo> {
public WordInfo(String word, int count) {
public int compareTo(WordInfo that) {
return this.count == that.count ? this.word.compareTo(that.word) : that.count - this.count;
public AutocompleteSystem(String[] sentences, int[] times) {
for (int i = 0; i < sentences.length; i++) {
trie.insert(sentences[i], times[i]);
public List<String> input(char c) {
List<String> res = new ArrayList<>();
TrieNode node = trie.search(prefix);
PriorityQueue<WordInfo> maxHeap = new PriorityQueue<>();
for (String key : node.count.keySet()) {
maxHeap.add(new WordInfo(key, node.count.get(key)));
for (int i = 0; i < 3 && !maxHeap.isEmpty(); i++) {
res.add(maxHeap.remove().word);
* Your AutocompleteSystem object will be instantiated and called as such:
* AutocompleteSystem obj = new AutocompleteSystem(sentences, times);
* List<String> param_1 = obj.input(c);