Short & Simple | Clean C++ with explaination | INTUITIVE Binary Search |
Instead of checking if the given word is a subsequence of the string s, We just need to store which character occurs at what position, Because ith character of 
Instead of checking if the given word is a subsequence of the string s, We just need to store which character occurs at what position, Because ith character of a subsequence must occur after the (i-1)th character in the original string s.\nThis leads us to binary search, We can store the occurences of each character in a vector.\nLets maintain a variable last which will store the position of the (i-1)th character of the subsequence in the original string s.\nso if there is an occurence of the ith character in the original string after the position of last i.e. (i-1)th character, increment the ans by 1 and update last equal to the position of the current character in the original string s.\nIf there exist a position for current character in the original string after the position of (i-1)th character, its possible to add this character to the subsequence other wise its impossible. \nTo implement the same idea we can do binary search and find the next value greater than last in the current character\'s occurences.\n```\nclass Solution {\npublic:\n    int numMatchingSubseq(string s, vector<string>& words) {\n        vector<int> a[26];\n        int ans = 0, n = s.length();\n        for(int i = 1;i<=n;i++){\n            a[s[i-1]-\'a\'].push_back(i);\n        }\n        for(auto word:words){\n            int last = 0;\n            bool poss = true;\n            for(auto ch : word){\n                int ind = upper_bound(a[ch-\'a\'].begin(),a[ch-\'a\'].end(),last) - a[ch-\'a\'].begin();\n                if(ind == a[ch-\'a\'].size()){\n                    poss = false;\n                    break;\n                } else {\n                    last = (a[ch-\'a\'])[ind];\n                }\n            }\n            if(poss)ans++;\n        }\n        return ans;\n    }\n};\n```
[]