[C++] | Binary Search & Map | Example & Comments
First try this problem , if you have\'nt {with DP and two pointer approach} :  392. Is Subsequence\n##### Tracing example for one string , we have to just apply
##### **First try this problem , if you have\'nt {with DP and two pointer approach} :  [392. Is Subsequence](https://leetcode.com/problems/is-subsequence/)**\n##### **Tracing example for one string , we have to just apply to all strings .**\n\t\t\t\t\t\t\t\t    \n    Example for finding subseqence : \n\t\t 0  1  2  3  4  5  6  7  8  9\n\ts = "d  s  a  h  j  p  j  a  u  f" , w[i] = "a  h  j  p j  a u" \n    map contains -   \n\t\t\t\t\t  m[d] = {0} \n                      m[s] = {1}\n                      m[a] = {2,7}\n                      m[h] = {3}\n                      m[j] = {4,6}\n                      m[p] = {5}\n                      m[u] = {8}\n                      m[f] = {9}\n    Upper Bound defination = Upper Bound returns an iterator pointing to the first element in the \n                             range [first, last) that is greater than value, or last if no such \n                             element is found. It takes log(n) time if array is sorted .\n                                    \n    1. curr = -1 ,finding upper bound in m[a] with curr = -1, we get pos = curr = 0.\n    2. curr = 1  , upper_bound(m[\'h\'] , curr ) = 3\n    3. curr = 3  , upper_bound(m[\'j\'] , curr ) = 4\n    4. curr = 4  , upper_bound(m[\'p\'] , curr ) = 5\n    5. curr = 5  , upper_bound(m[\'j\'] , curr ) = 6\n    6. curr = 6  , upper_bound(m[\'a\'] , curr ) = 7\n    7. curr = 7  , upper_bound(m[\'u\'] , curr ) = 8\n       return True ( as we did\'nt encountered any false conditions)\nTime Complexity : O(n) for building map  + O(no.of words * max len of word * finding position with upper_bound) = O(n + m* len * log(n)) \nSpace complesity : O(26) for the given string + O(m) for storing differnt words if they are\'nt unique.\n\nInstead of storing unique words , we can also use dynamic programming to store true/false for each word.\n#### CODE \n```               \n    bool issubseq(string &str,unordered_map<char,vector<int>> &m){\n        int curr_idx = -1;\n        for(int j=0;j<str.length();j++){\n            auto pos = upper_bound(m[str[j]].begin(),m[str[j]].end(),curr_idx);\n            \n            //if all the characters before the current index is consumed then return false\n            if(pos == m[str[j]].end())\n                return false;\n            curr_idx = m[str[j]][pos - m[str[j]].begin()];   \n        }\n        return true;\n    }\n    int numMatchingSubseq(string s, vector<string>& words) {\n        //to store the character position of string\n        unordered_map<char,vector<int>> m;\n        for(int i=0;i<s.length();i++)\n            m[s[i]].push_back(i);\n        \n        //to get rid of duplicate query elements ,\n        //second element of map will give frequency of repetition\n        unordered_map<string,int> w;\n        for(auto &str:words)\n            w[str]++;\n\n        int ret = 0;\n        //for each query word find subsequence\n        for(auto &word:w){\n            string str = word.first;\n            if(issubseq(str,m))\n                ret+= word.second;\n        }\n        return ret;\n    }\n```
[]