O(n) || CPP
\n# Approach\ndp[i] stores the length of the longest suffix of word2 that we can match using the substring word1[i: ]\n\n# Code\ncpp []\nclass Solution {\npubli
\n# Approach\ndp[i] stores the length of the longest suffix of word2 that we can match using the substring word1[i: ]\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    vector<int> validSequence(string word1, string word2) {\n        int n=word1.size(),m=word2.size();\n        vector<int>dp(n+1,0);\n        int j=m-1;\n        for(int i=n-1;i>=0;--i){\n            dp[i]=dp[i+1];\n            if(j==-1)continue;\n            if(word1[i]==word2[j]){--j;dp[i]++;}\n        }vector<int>ans;\n        for(int i=0;i<n;++i){\n            if(ans.size()==m)break;\n            if(word1[i]==word2[ans.size()])ans.push_back(i);\n            else if(dp[i+1]>=m-ans.size()-1){ans.push_back(i);break;}\n             \n        }if(ans.size()==m)return ans;\n        int i=ans.empty()?0:ans.back()+1;j=ans.size();\n        if(dp[i]<m-j)return {};\n        while(j<m){\n            if(word1[i]==word2[j]){ans.push_back(i);++j;}\n            ++i;\n        }return ans;\n\n    }\n};\n```
['Dynamic Programming', 'C++']