**Approach** **1. Create a frequency map** `unordered_map>> mp` stores each `word -> nextWord` pair. For every pair: - `first` stores the frequency. - `second` stores the order in which the pair was first encountered. **2. Count the frequency** For every sequence, each adjacent `word -> nextWord` pair is processed. If the pair already exists, its frequency is incremented. Otherwise, its frequency is set to `1` and a new increasing `order` value is assigned. The order remains unchanged when the same pair occurs again. **3. Find the best next word for every word** For every word, all its possible next words are traversed. The next word with: - Higher frequency is selected. - If frequencies are equal, the one with smaller `order` is selected. The selected next word is stored in `mp_next_word`. **4. Process the queries** For every query: - If the word exists in `mp_next_word`, its corresponding next word is added to the answer. - Otherwise, `nullopt` is added. **5. Complexity** Let `N` be the total number of adjacent pairs and `U` be the number of distinct `word -> nextWord` pairs. Time Complexity: `O(N + U + Q)` where `Q` is the number of queries. Space Complexity: `O(U)` The hash maps store the distinct `word -> nextWord` pairs and the best next word for each word. **6. Full Code** ``` #include #include #include using namespace std; struct compare { bool operator()(pair> &a, pair> &b){ if(a.first!=b.first) return a.firstb.second.first; } }; class Solution { public: vector> predictNextWords(const vector>& seq, const vector& queries) { int seqSize = seq.size(); unordered_map>> mp; unordered_map mp_next_word; int order = 0; for(int i=0;i> maxi = {"",{INT_MIN,INT_MAX}}; for(auto &key: word.second){ if( (key.second.first>maxi.second.first) || (key.second.first==maxi.second.first && key.second.second> ans; for(int i=0;i

Visa Sponsors

H-1B Odds Calculator

Visa Bulletin

Quick Overview

Predict the Most Frequent Next Word in Constant Time