C++ Solution | 90% Faster | Easy Understanding | Binary Search | Hashmap
\nclass Solution {\npublic:\n    int bs(vector<int> &arr, int x){\n        int start = 0;\n        int end = arr.size()-1;\n        int ans = -1;\n        while
```\nclass Solution {\npublic:\n    int bs(vector<int> &arr, int x){\n        int start = 0;\n        int end = arr.size()-1;\n        int ans = -1;\n        while (start <= end)\n        {\n            int mid = (start + end) / 2;\n\n            if (arr[mid] <= x)\n                start = mid + 1;\n            else\n            {\n                ans = mid;\n                end = mid - 1;\n            }\n        }\n        return ans==-1 ? ans : arr[ans];\n    }\n    \n\n    int numMatchingSubseq(string s, vector<string>& words) {\n\t\n\t\t// First , we are mapping index of characters of given string to respective characters\n        unordered_map<char,vector<int>> mp;\n        for(int i=0;i<s.length();i++){\n            mp[s[i]].push_back(i);\n        }\n          \n        int count = words.size(); // initializing ans \n\t\t\n        for(auto w : words){\n            int prev = -1;\n            for(int j=0;j<w.size();j++){\n\t\t\t\t// Searching for strictly greater element than prev using binary search\n                int x = bs(mp[w[j]],prev);\n\t\t\t\t// If strictly greater element not found, the current subsequence cannot be formed.\n                if(x == -1){\n                    count--;\n                    break;\n                }\n\t\t\t\t// Else, updating the prev\n                else{\n                    prev = x;\n                }\n            }\n        }\n        return count;\n    }\n};\n```\n\n\nPS: You can use C++ STL function upper bound instead of writing binary search code manually\n\n\n**Time Complexity : O( M * S * log(N) ) \nSpace Complexity : O( N ) ,**\n where M is length of words array, S is length of a word and N is length of given string
['String', 'C', 'Sorting', 'Binary Tree']