Solved using unordered map,fully explained.
map\n#Time complexity:\ngroups words by their last character using an unordered_map (m) instead of a vector of vectors. The rest of the logic for iterating thro
map\n#Time complexity:\ngroups words by their last character using an unordered_map (m) instead of a vector of vectors. The rest of the logic for iterating through the characters of the string, processing words, and updating the count remains the same.\n\n\n\nThe initial loop that groups words by their last character still takes O(N) time, where N is the total number of characters in all words combined.\nThe second loop iterates through the characters of the string, and for each character, the processing takes O(K) time, where K is the average number of words that end with that character.\nThe overall time complexity is also O(N + K * M)\n\n# Code\n```\nclass Solution {\npublic:\n    int numMatchingSubseq(string S, vector<string>& words) {\n    int cnt = 0;  // Counter for matching subsequences\n    unordered_map<char, vector<string>> m;  // Using an unordered_map to group words by their last character\n    \n    // Group words by their last character\n    for (auto& word : words)\n        m[word.back()].push_back(word);\n    \n    // Iterate through the characters of the string in reverse order\n    for (int i = (int)S.size() - 1; i >= 0; --i) {\n        char c = S[i];  // Current character\n        auto bucket = m[c];  // Get words that end with the current character\n        m[c].clear();  // Clear the bucket\n        \n        // Iterate through words in the bucket\n        for (auto& word : bucket) {\n            word.pop_back();  // Remove the last character from the word\n            \n            if (word.empty())\n                ++cnt;  // If the word becomes empty, it\'s a subsequence, so increment the counter\n            else\n                m[word.back()].push_back(word);  // Put the word into the appropriate bucket based on its new last character\n        }\n    }\n    \n    return cnt;  // Return the count of matching subsequences\n}\n\n    };\n```
['Greedy', 'Ordered Map', 'C++']