C++ SOLUTION || LEETCODING
Intuition\nSolution on youtube \nwww.youtube.com/watch?v=W-hOpEMSaQI\n# Approach\n\n# Complexity\n- Time complexity:\n Add your time complexity here, e.g. O(n) 
# Intuition\nSolution on youtube \nwww.youtube.com/watch?v=W-hOpEMSaQI\n# Approach\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    vector<int> validSequence(string w1, string w2) {\n        int n = w1.size();\n        int m = w2.size();\n\n        int dp[n + 1];\n        dp[n] = 0;\n\n        int i = n - 1;\n        int j = m - 1;\n\n        while (i >= 0) {\n            if (j>=0 && w1[i] == w2[j]) {\n                dp[i] = dp[i + 1] + 1;\n                i--;\n                j--;\n                \n            } else {\n                dp[i] = dp[i + 1];\n                i--;\n                \n            }\n        }\n    \n        vector<int>ans;\n        vector<int>res;\n        int flag = 0;\n        i=0;\n        j=0;\n\n        while(i<n && j<m)\n        {\n           if(w1[i]!=w2[j])\n           {\n             if(!flag  && dp[i+1]>=m-j-1)\n             {\n                   flag = 1;\n                   ans.push_back(i);\n                   j++;\n             }\n           }\n           else\n           {\n             ans.push_back(i);\n             j++;\n           }\n\n           i++;\n        }\n       \n        return j!=m ? res:ans;\n    }\n};\n```
['C++']