Design a search query autocomplete system | hard | MUST DO

https://practice.geeksforgeeks.org/problems/search-query-auto-complete/1?page=2&difficulty[]=1&difficulty[]=2&status[]=unsolved&category[]=Dynamic%20Programming&category[]=Binary%20Search&category[]=Trie&category[]=union-find&sortBy=submissions

Design a search query autocomplete system for a search engine.

The users will input a sentence ( which may have multiple words and ends with special character '#').

For each character they type except '#', you need to return the top 3 previously entered and most frequently queried sentences that have prefix the same as the part of sentence already typed.

Here are the specific rules:

The frequency for a sentence is defined as the number of times a user typed the exactly same sentence before.
The returned top 3 sentences should be sorted by frequency (The first is the most frequent).  If several sentences have the same frequency, you need to use ASCII-code order (smaller one appears first).
If less than 3 valid sentences exist, then just return as many as you can.
When the input is a special character, it means the sentence ends, and in this case, you need to return an empty list.


Your job is to implement the methods of the AutoCompleteSystem:

AutoCompleteSystem(String[] sentences, int[] times): This is the constructor. The input is previously used data. Sentences is a string array consists of previously typed sentences. Times is the corresponding times a sentence has been typed. Your system should record these historical sentences.
Now, the user wants to input a new sentence. The following function will provide the next character the user types:

String[] input(char c): The input c is the next character typed by the user. The character will only be lower-case letters ('a' to 'z'), blank space (' ') or a special character ('#'). Also, the previously typed sentence should be recorded in your system. The output an array will be the top 3 historical sentences that have prefix the same as the part of sentence already typed.


Example:
Operation:
AutoCompleteSystem(["i love you", "island",
"ironman", "i love geeksforgeeks"], [5,3,2,2])
The system have already tracked down the
following sentences and their corresponding
times:
"i love you" : 5 times
"island" : 3 times
"ironman" : 2 times
"i love geeksforgeeks" : 2 times
Now, the user begins another search:
Operation: input('i')
Output:
["i love you", "island","i love geeksforgeeks"]
Explanation:
There are four sentences that have prefix
"i". Among them, "ironman" and "i love
geeksforgeeks" have same frequency. Since
' ' has ASCII code 32 and 'r' has ASCII code
 114, "i love geeksforgeeks" should be in
front of "ironman". Also we only need to
output top 3 most frequent sentences, so
"ironman" will be ignored.
Operation: input(' ')
Output: ["i love you","i love geeksforgeeks"]
Explanation:
There are only two sentences that have prefix
"i ".
Operation: input('a')
Output: []
Explanation:
There are no sentences that have prefix "i a"
Operation: input('#')
Output: []
Explanation:
The user finished the input, the sentence
"i a" should be saved as a historical
sentence in system. And the next input
will be counted as a new search.

---------------------------------------------------------------------------------------------------------------------------------------

BRUTE FORCE

struct TrieNode{
    TrieNode* children[256]={nullptr};
    bool isTerminal;
    TrieNode(){
        isTerminal=false;
    }
};

struct cmp{
    bool operator()(pair<int,string> &P1, pair<int,string> &P2){
        if(P1.first==P2.first){
            string sentence1=P1.second;
            string sentence2=P2.second;
            int result=sentence1.compare(sentence2);
            return result<0;
            }
        return P1.first>P2.first;
    }
};

class AutoCompleteSystem {
private:
    priority_queue<pair<int,string>,vector<pair<int,string>>,cmp> pq;
    string inProgress="";
    TrieNode* root;
    unordered_map<string,int> count;
public:
    void insert(string &str){
        TrieNode* pCrawl=root;
        for(auto c: str){
            if(pCrawl->children[c]==NULL){
                pCrawl->children[c]=new TrieNode();
            }
            pCrawl=pCrawl->children[c];
        }
        pCrawl->isTerminal=true;
    }

    AutoCompleteSystem(vector<string>& sentences, vector<int>& times) {
        root=new TrieNode();
        for(int i=0;i<sentences.size();i++){
            insert(sentences[i]);
            count[sentences[i]]=times[i];
        }
    }

    bool isLeaf(TrieNode* node){
        for(int i=0;i<256;i++){
            if(node->children[i]!=nullptr){
                return false;
            }
        }
        return true;
    }

    void search(TrieNode* root, string &prefix, string builder, int curr){
        if(curr==prefix.size()){
            if(root->isTerminal==true){
                pq.push({count[builder],builder});
                if(pq.size()>3){
                    pq.pop();
                }
            }
            if(isLeaf(root)==true){
                return;
            }
            for(int i=0;i<256;i++){
                if(root->children[i]!=nullptr){
                    search(root->children[i],prefix,builder+char(i),curr);
                }
            }
            return;
        }


        if(root->children[prefix[curr]]!=nullptr){
            search(root->children[prefix[curr]],prefix,builder+prefix[curr],curr+1);
        }
    }

    vector<string> input(char c) {
        vector<string> res;
        if(c=='#'){
            insert(inProgress);
            count[inProgress]++;
            inProgress="";
            return res;
        }
        inProgress+=c;
        search(root,inProgress,"",0);
        while(!pq.empty()){
            res.push_back(pq.top().second);
            pq.pop();
        }
        reverse(res.begin(),res.end());
        return res;
    }
};
---------------------------------------------------------------------------------------------------------------------------------------

SEMI OPTIMAL APPROACH

Optimization is be done here. The idea is to keep storing the words as you go in the node. This way the search is limited to prefix only and you wouldn't need to search all words


struct TrieNode{
    TrieNode* children[256]={nullptr};
    unordered_set<string> words;
    TrieNode(){}
};

struct cmp{
    bool operator()(pair<int,string> &P1, pair<int,string> &P2){
        if(P1.first==P2.first){
            string sentence1=P1.second;
            string sentence2=P2.second;
            int result=sentence1.compare(sentence2);
            return result<0;
            }
        return P1.first>P2.first;
    }
};

class AutoCompleteSystem {
private:
    TrieNode* root;
    string inProgress="";
    unordered_map<string,int> count;
    priority_queue<pair<int,string>,vector<pair<int,string>>,cmp> pq;
public:
    AutoCompleteSystem(vector<string>& sentences, vector<int>& times) {
        root=new TrieNode();
        for(int i=0;i<sentences.size();i++){
            insert(sentences[i]);
            count[sentences[i]]=times[i];
        }
    }

    void insert(string &str){
        TrieNode* pCrawl=root;
        for(auto c: str){
            if(pCrawl->children[c]==NULL){
                pCrawl->children[c]=new TrieNode();
            }
            pCrawl=pCrawl->children[c];
            (pCrawl->words).insert(str);
        }
        (pCrawl->words).insert(str);
    }

    vector<string> input(char c) {
        if(c=='#'){
            insert(inProgress);
            count[inProgress]++;
            inProgress="";
            return {};
        }
        vector<string> res;
        inProgress+=c;
        TrieNode* ptr=root;
        int i=0;
        while(i<inProgress.size() && ptr->children[inProgress[i]]!=NULL){
            ptr=ptr->children[inProgress[i]];
            i++;
        }
        if(i==inProgress.size()){
            unordered_set<string> WORDS=ptr->words;
            for(auto word: WORDS){
                pq.push({count[word],word});
                if(pq.size()>3){
                    pq.pop();
                }
            }
            while(!pq.empty()){
                res.push_back(pq.top().second);
                pq.pop();
            }
            reverse(res.begin(),res.end());
        }
        return res;
    }
};

---------------------------------------------------------------------------------------------------------------------------------------

OPTIMAL ANSWER

Can you optimise it even furthur??...Well, if you think, we are searching for this inProgress again and again for just one word addition. Let us say inProgress currently is "i hate you reader" and let us say, we add c to it, so it becomes "i hate you readerc", now that is not available. SO, it does not matter how many words get attached now, you will never ever get any answer.

Keep a tracker that tracks the current node we are right on. If you add a new letter and that is unavailable in tracker's children. Mark the tracker something so no matter what letters we attach, tracker will notify that no answer exist.. Else, just move the tracker forward :)


struct TrieNode{
    TrieNode* children[256]={nullptr};
    unordered_set<string> words;
    TrieNode(){}
};

struct cmp{
    bool operator()(pair<int,string> &P1, pair<int,string> &P2){
        if(P1.first==P2.first){
            string sentence1=P1.second;
            string sentence2=P2.second;
            int result=sentence1.compare(sentence2);
            return result<0;
        }
        return P1.first>P2.first;
    }
};

class AutoCompleteSystem {
private:
    TrieNode* tracker;
    TrieNode* root;
    string inProgress="";
    unordered_map<string,int> count;
    priority_queue<pair<int,string>,vector<pair<int,string>>,cmp> pq;
public:
    AutoCompleteSystem(vector<string>& sentences, vector<int>& times) {
        root=new TrieNode();
        for(int i=0;i<sentences.size();i++){
            insert(sentences[i],times[i]);
        }
        tracker=root;
    }

    void insert(string &str, int freq){
        if(count.find(str)!=count.end()){
            count[str]+=freq;
            return;
        }
        TrieNode* pCrawl=root;
        for(auto c: str){
            if(pCrawl->children[c]==NULL){
                pCrawl->children[c]=new TrieNode();
            }
            pCrawl=pCrawl->children[c];
            pCrawl->words.insert(str);
        }
        count[str]=freq;
    }

    vector<string> input(char c) {
        if(c=='#'){
            insert(inProgress,1);
            inProgress="";
            tracker=root;
            return {};
        }
        inProgress+=c;
        vector<string> res;
        if(tracker==nullptr){
            return res;
        }
        if(tracker->children[c]!=nullptr){
            tracker=tracker->children[c];
            for(auto word: tracker->words){
                pq.push({count[word],word});
                if(pq.size()>3){
                    pq.pop();
                }
            }
            while(!pq.empty()){
                res.push_back(pq.top().second);
                pq.pop();
            }
            reverse(res.begin(),res.end());
        }
        else{
            tracker=nullptr; // because no matter what, any furthur additions to inProgress would not yeild any answer anyways
        }
        return res;
    }
};