Problem Statement

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".

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

Constraints:

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

Problem Link

Number of Matching Subsequences - LeetCode

Code

class Solution {
public:
    int numMatchingSubseq(string s, vector<string>& words) {
        
        int res = 0;
        
        vector<vector<int>> alpha(26);
        int n = s.size();
        
        for(int i=0;i<n;i++)
        {
            alpha[s[i]-'a'].push_back(i);
        }
        
        for(string word:words)
        {
            bool found = true;
            int pos = -1;
            
            for(char ch:word)
            {
               
                auto itr = upper_bound(alpha[ch-'a'].begin(),alpha[ch-'a'].end(),pos);
                
                if(itr==alpha[ch-'a'].end())
                {
                    found = false;
                   
                }
                else 
                     pos = *itr;
                
                
            }
            if(found)
                res++;
            
            
        }
        
        return res;
        
    }
};