C++ Solutions one with HashMap + Binary Search , other with Hashmap
\n    /*\n     * Approach followed is a Hashmap + Binary search\n     * where we save all indices of each char of s in a map ie..,\n     * Eg:  s = abacedba\n  
```\n    /*\n     * Approach followed is a Hashmap + Binary search\n     * where we save all indices of each char of s in a map ie..,\n     * Eg:  s = abacedba\n     *            key   value\n     *     map =  [a]   0, 2, 7\n     *            [b]   1, 6\n     *            [c]   3\n     *            [e]   4\n     *\n     * Now traverse each word in the input vector and check whether it is a\n     * subsequence of s using a binary search approach\n     *\n     * Eg:  word = aad, traverse each char by char\n     *   As a is present twice and in the map when we check for the 2nd char a\n     * then we need to take the 2nd index instead of the 1st index. \n     *\n    */\n    int numMatchingSubseq(string s, vector<string>& words) {\n        // Initialize a map to store the indicies of all chars in s\n        unordered_map<char, vector<int>> mp;\n        \n        // Traverse all the chars in s and add the indices to map\n        for (int i = 0; i < s.length(); i++) {\n            // push the index to map for the current char\n            // The indices will be in ascending order for the character\n            mp[s[i]].push_back(i);\n        }\n        \n        // Variable to store result\n        int numSubseq = 0;\n        \n        // Temporary variables\n        int low;\n        bool isSubseq;\n        \n        // Traverse all the words of the input \n        for (string& word: words) {\n            // Lower Index\n            // Index that needs to be found should be greater than this low index\n            low = -1;\n            // Assume current word is a subsequence\n            isSubseq = true;\n            \n            for (char& ch : word) {                \n                // Perform a binary search \n                int pos = upper_bound(mp[ch].begin(), mp[ch].end(), low) - mp[ch].begin();\n                // Check if the current char is present in map or not\n                if (pos == mp[ch].size()) {\n                    // no such char present,\n                    isSubseq = false;\n                    break;\n                }\n                \n                low = mp[ch][pos];\n            }\n\n            // Increment result if current word is subsequence of s\n            numSubseq += isSubseq;\n        }\n        \n        return numSubseq;\n    }\n\n    /*\n     * Approach followed is a Hashmap, which stores all the words of\n     * same starting char into vector\n     *\n     * Traverse a loop that goes for all chars in s.\n     *   . Retrieve the vector of words and delete the current char key from map\n     *   . Retrieve all words which starts with current char, remove the starting\n     *     char, if they are empty then that word is a subsequence increase the\n     *     result.\n     *   . Push the words based on the new starting char to map\n     *\n     *\n    */\n    int numMatchingSubseq(string s, vector<string>& words) {\n        // Initialize a map to store the indicies of all chars in s\n        unordered_map<char, vector<string>> mp;\n        \n        // Traverse all words from the input and arrange it based on starting char\n        for (string& word : words) {\n            mp[word[0]].push_back(word);\n        }\n        \n        // Variable to store result\n        int numSubseq = 0;\n        \n        // Traverse all the chars in string s\n        for (char& ch : s) {\n            // check if key(current char) is available at map\n            if (mp.count(ch) == 1) {\n                // Retrieve all words that starts with current char\n                vector<string> wrds(mp[ch]);\n                \n                // Delete the current entry in queue\n                mp.erase(ch);\n                \n                // Traverse all words that starts with current char\n                for (string& word : wrds) {\n                    // check if the current word has only one char\n                    if (word.size() == 1) {\n                        // current word size is only 1 char, then this word is a subsequence\n                        // of input string s\n                        numSubseq++;\n                    }\n                    else {\n                        // push the word to map based on the starting char excluding the current char\n                        // Remove the first char and push the words to mp based on starting char\n                        mp[word[1]].push_back(word.substr(1));\n                    }\n                }\n            }\n        }\n        \n        return numSubseq;\n    }\n```
[]