792. Number of Matching Subsequences

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

• Time : O(m n log k)
  • m is size of words
  • n is length of word
  • k is length of s
• Space : O(1) (constant)

class Solution {
public:
    int numMatchingSubseq(string s, vector<string>& words) {
        vector<vector<int>> arr(26, vector<int>());
        for(int i = 0; i < s.length(); i++) { //push index char of S
            arr[s[i] - 'a'].push_back(i);
        }
        
        int res = 0;
        
        for(auto& word : words) { //O(m n log k)
            int index = 0;
            bool match = true;
            for(auto ch : word) { //find each word can be in smallest index
                auto it = lower_bound(arr[ch-'a'].begin(), arr[ch-'a'].end(), index);
                if(it == arr[ch-'a'].end()) {
                    match = false;
                    break;
                }
                index = *it + 1;
            }
            if(match) res += 1;
        }
        
        return res;
    }
};