3 Different Approach (All correct solutions) | TLE to best Approach | C++
Passed all test cases , but TLE in sol-1.\n0(N +  M  * L)  \nN= length of string s\nM = No of words\nL = max length of a word in words.\nclass Solution {\npubli
Passed all test cases , but TLE in sol-1.\n0(N +  M  * L)  \nN= length of string s\nM = No of words\nL = max length of a word in words.\nclass Solution {\npublic:\n    int numMatchingSubseq(string s, vector<string>& words) {\n        \n        unordered_map<char,vector<int>> ump; // char, index\n        int ans=0;\n        int n = s.length();\n        \n        for(int i=0;i<n;i++){\n            ump[s[i]].push_back(i);\n        }\n        unordered_map<string,int> wordMap;\n        \n        for(int k=0;k<words.size();k++){\n            wordMap[words[k]]++;\n        }\n        \n        for(auto it:wordMap){\n            \n            string w = it.first;\n            int m = w.length();\n            if(m > n){\n                continue;\n            }\n            int currIdx = -1,flag = 1;\n            \n            for(int i=0;i<m;i++){\n                \n                if(ump.find(w[i])!=ump.end()){\n                    \n                    vector<int> index = ump[w[i]];\n                    int tempIdx = currIdx;\n                    \n                    for(int j=0;j<index.size();j++){\n                        \n                        if(index[j] > currIdx) {\n                            currIdx = index[j];\n                            break;\n                        }\n                    }\n                    \n                    if(tempIdx == currIdx){\n                        flag = 0;\n                        break;\n                    }\n                } else {\n                    flag = 0;\n                    break;\n                }\n            }\n            \n           if(flag) {\n               ans = ans + it.second;\n           }\n        }\n        return ans;\n    }\n};\n\n0(N + M * log L)\nN= length of string s\nM = No of words\nL = max length of a word in words.\n\nclass Solution {\npublic:\n    int numMatchingSubseq(string s, vector<string>& words) {\n        \n        int n = s.length();\n        unordered_map<string,int> wump;\n        unordered_map<char,vector<int>> sump;\n        \n        for(auto w:words){\n            wump[w]++;\n        }\n        \n        for(int i=0;i<n;i++){\n            sump[s[i]].push_back(i);\n        }\n        \n        int ans=0;\n        for(auto it : wump){\n            \n            string subs = it.first;\n            int m = subs.length();\n            if(m > n){\n                continue;\n            }\n            int currIdx = -1,status = 1;\n            \n            for(int i=0;i<m;i++){\n                \n                if(sump.find(subs[i])!=sump.end()){\n                    \n                    vector<int> &index = sump[subs[i]];\n                    int beg = 0,end = index.size()-1;\n                    \n                    while(beg<=end){\n                        int mid = beg+(end-beg)/2;\n                        \n                        if(currIdx >= index[mid]){\n                            beg = mid+1;\n                        } else {\n                            end = mid-1;\n                        }\n                    }\n                    if(beg >= index.size()){\n                        status=0;\n                        break;\n                    }\n                    currIdx = index[beg];  \n                } else {\n                    status = 0;\n                    break;\n                }\n            }\n            \n            if(status){\n                ans = ans + it.second;\n            }\n            \n        }\n        \n        return ans;\n    }\n};\n\n0(N * 2^N)\nN= length of string s\n2^N = Max unique subseq\n\nclass Solution {\npublic:\n    bool isSubseq(string &s,string &subs){\n        \n        int n = s.length();\n        int m = subs.length();\n        \n        int i=0,j=0;\n        \n        while(i<n && j<m){\n            \n            if(s[i]==subs[j]){\n                i++; j++;\n            } else{\n                i++;\n            }\n        }\n        \n        if(j==m){\n            return true;\n        }\n        \n        return false;\n    }\n    int numMatchingSubseq(string s, vector<string>& words) {\n        \n        int n = s.length();\n        unordered_map<string,int> wump;\n        \n        for(auto w:words){\n            wump[w]++;\n        }\n        \n        int ans=0;\n        for(auto it : wump){\n            \n            string subs = it.first;\n            if(isSubseq(s,subs)){\n                ans += it.second;\n            }\n        }\n        \n        return ans;\n    }\n};
[]