<p>Given a string <code>s</code> and an array of strings <code>words</code>, return <em>the number of</em> <code>words[i]</code> <em>that is a subsequence of</em> <code>s</code>.</p>

<p>A <strong>subsequence</strong> of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.</p>

<ul>
	<li>For example, <code>&quot;ace&quot;</code> is a subsequence of <code>&quot;abcde&quot;</code>.</li>
</ul>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;abcde&quot;, words = [&quot;a&quot;,&quot;bb&quot;,&quot;acd&quot;,&quot;ace&quot;]
<strong>Output:</strong> 3
<strong>Explanation:</strong> There are three strings in words that are a subsequence of s: &quot;a&quot;, &quot;acd&quot;, &quot;ace&quot;.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;dsahjpjauf&quot;, words = [&quot;ahjpjau&quot;,&quot;ja&quot;,&quot;ahbwzgqnuk&quot;,&quot;tnmlanowax&quot;]
<strong>Output:</strong> 2
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= s.length &lt;= 5 * 10<sup>4</sup></code></li>
	<li><code>1 &lt;= words.length &lt;= 5000</code></li>
	<li><code>1 &lt;= words[i].length &lt;= 50</code></li>
	<li><code>s</code> and <code>words[i]</code> consist of only lowercase English letters.</li>
</ul>

class Solution {
public:
    int numMatchingSubseq(string S, vector<string>& words) {
    int cnt = 0;  // Counter for matching subsequences
    unordered_map<char, vector<string>> m;  // Using an unordered_map to group words by their last character
    
    // Group words by their last character
    for (auto& word : words)
        m[word.back()].push_back(word);
    
    // Iterate through the characters of the string in reverse order
    for (int i = (int)S.size() - 1; i >= 0; --i) {
        char c = S[i];  // Current character
        auto bucket = m[c];  // Get words that end with the current character
        m[c].clear();  // Clear the bucket
        
        // Iterate through words in the bucket
        for (auto& word : bucket) {
            word.pop_back();  // Remove the last character from the word
            
            if (word.empty())
                ++cnt;  // If the word becomes empty, it's a subsequence, so increment the counter
            else
                m[word.back()].push_back(word);  // Put the word into the appropriate bucket based on its new last character
        }
    }
    
    return cnt;  // Return the count of matching subsequences
}

    };
191749