Given a string s and an array of strings words, return the number of words[i] that is a subsequence of s.

A subsequence 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.


	For example, "ace" is a subsequence of "abcde".


&nbsp;
Example 1:

Input: s = "abcde", words = ["a","bb","acd","ace"]
Output: 3
Explanation: There are three strings in words that are a subsequence of s: "a", "acd", "ace".


Example 2:

Input: s = "dsahjpjauf", words = ["ahjpjau","ja","ahbwzgqnuk","tnmlanowax"]
Output: 2


&nbsp;
Constraints:


	1 &lt;= s.length &lt;= 5 * 104
	1 &lt;= words.length &lt;= 5000
	1 &lt;= words[i].length &lt;= 50
	s and words[i] consist of only lowercase English letters.


class Solution:
    def numMatchingSubseq(self, s: str, words: List[str]) -> int:
        word_dict = defaultdict(list)
        numMatch = 0
        # add words into bucket with key as order of the first letter
        for w in words:
            word_dict[ord(w[0])-ord('a')].append(w)
        # loop through the characters in s
        for c in s:
            qualified = word_dict[ord(c)-ord('a')]
            word_dict[ord(c)-ord('a')] = []
            for q in qualified:
                # if the word starts with the specified letter. i.e this is the last letter of the word
                if len(q) == 1:
                    numMatch += 1
                else:
                    word_dict[ord(q[1])-ord('a')].append(q[1:])
        return numMatch
class Solution {
    public int numMatchingSubseq(String s, String[] words) {
        int count = 0;
        Map<String, Integer> map = new HashMap<>();
        for(String word : words){
            if(!map.containsKey(word)){
                map.put(word, 1);
            }
            else{
                map.put(word, map.get(word)+1);
            }
        }
        for(String word : map.keySet()){
            if(isSeq(word, s)){
                count += map.get(word);
            }
        }
        return count;
    }
    public boolean isSeq(String s1, String s2){
        int s1ind = 0;
        int s2ind = 0;
        int counter = 0;
        if(s1.length() > s2.length()){
            return false;
        }
        while(s1ind < s1.length() && s2ind < s2.length()){
            if(s1.charAt(s1ind) == s2.charAt(s2ind)){
                counter++;
                s1ind++;
                s2ind++;
            }
            else{
                s2ind++;
            }
        }
        return counter == s1.length();
    }
}
class Solution {
public:
    int numMatchingSubseq(string s, vector<string>& words) {
       int ct=0;
        unordered_map<string,int>m;
        
        for(int i=0;i<words.size();i++)
        {
             m[words[i]]++;
        }
        
        
        for(auto it=m.begin();it!=m.end();it++)
        {
            string k=it->first;
            
            int z=0;
            
            for(int i=0;i<s.length();i++)
            {
                if(s[i]==k[z])
                    z++;
                else if(z==k.length())
                    break;
            }
            if(z==k.length())
                ct=ct+it->second;
            
        }        
    return ct;
    }
};
var numMatchingSubseq = function(s, words) {
    let subsequence = false;
    let count = 0;
    let prevIdx, idx 
    for(const word of words) {
        prevIdx = -1;
        idx = -1;
        subsequence = true;
        for(let i = 0; i < word.length; i++) {
            idx = s.indexOf(word[i], idx + 1);
            if(idx > prevIdx) {
                prevIdx = idx;
            } else {
                subsequence = false;
                break;
            }
        }
        if(subsequence) count++;
    }
    return count;
};
Number of Matching Subsequences