Problem C of last weekly round.
Intuition\n First try to solve without any change. This is straight forward just use two pointer to solve.\nLest jump to main part \n\nlets define dp(n) here n 
# Intuition\n<!-- First try to solve without any change. This is straight forward just use two pointer to solve.\nLest jump to main part \n\nlets define dp(n) here n is the size of word1\n\ndp[i]  for all i  from 0.....n-1 refers how many char you can choose\nfrom word1 and the concatenation of this char would be a suffix of word2 and the picking point will start from i or greater.\n\n\nsuppose you want to change for j th char in word2 in word1 , Now for 0....j-1 th char of word2 should be find greedily using two pointer and you will have have another pointer pos that indicate you have to \ngo to pos position in word1 for obtain all of (0...j-1) of word2.\nSuppose word1[pos+1]==word2[j] then you dont need to do anything.\nother wise if(m-j<=dp[pos+2]>) then there should be a sub sequence \nof word1 and concatenation of the pos of sub sequence will be a suffix of word2 of len m-j.\n -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- O(N) -->\n\n- Space complexity:\n<!-- O(N) -->\n\n# Code\n```cpp []\nclass Solution {\npublic:\n   // #define pb push_back();\n    vector<int> validSequence(string word1, string word2) {\n        int n = word1.size();int m = word2.size();\n        string ss = word2;\n        vector<int>dp(n+2);int cnt=0;\n        for(int i=n-1;i>=0;i--){\n            if(word2.size() and word1[i]==word2.back()){\n                cnt++;word2.pop_back();\n            }\n            dp[i] = cnt;\n        }\n        word2 = ss;\n        int pos = -1;\n        vector<int>ans;\n        int ok=0;\n        for(int i=0;i<m and pos<n-1;i++){\n            if(ok==1){\n                if(word1[pos+1]==word2[i]){\n                  ans.push_back(++pos);\n                } \n                else{\n                    ++pos,i--;\n                }\n                continue;\n            }\n            if(word1[pos+1]==word2[i]){\n                  ans.push_back(++pos);\n                  continue;\n            }\n            int x = dp[pos+2];\n            if(m-i-1<=x){\n                ans.push_back(++pos);\n                ok=1;\n            }\n            else{\n                pos++;\n                i--;\n            }\n        }\n        if(ans.size()!=m)ans.clear();\n        return ans;\n    }\n};\n```
['C++']