Easy 1D DP approach with intuition | Beats 91% solutions
Intuition\n Describe your first thoughts on how to solve this problem. \nWe can redefine the problem as least index of word1 for which we can skip the wrong mat
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nWe can redefine the problem as least index of word1 for which we can skip the wrong match. Now we just need to find least index for which we can skip the wrong match and remaining string of word2 will match some subsequence of word1.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n## we will traverse word2 and word1 from rear. i=w1.size() and j=w2.size()\nwe will need a vector (let\'s say dp) to store possible index of w2 from rear to j so that from i to rear of w1 a subsequence can match it.\n\n## One  skip is allowed which is represented by flag = true;\n\n## now traverse the dp array from start index=0;\n\nif processed all indexs of word2 break loop as we got the answer;\n\nelse if both are equal then its okay to take it\n\nelse if if we have not skipped the wrong occurence and after skipping the current index we can get all the indexes of word2 from j+1 to last in the word1 from i+1 to last then we will add this index in our answer vector and beacuse we ignored this wrong occurence we will make the flag = false, so that we can\'t ignore wrong occurence again;\n\n\n## if size of answer array is less than size of word2 we have not been able to find all occurences hence return empty array else return answer array\n\n#This is my first post hope I was able to explain if You have any problem in understanding you can comment or any feedback is greatly appreciated\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(m+n)\nm=w1.size();\nn= w2.size()\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(m +n)\nm = dp array;\nn= answer vector\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    vector<int> validSequence(string w1, string w2) {\n        int m = w1.size(), n=w2.size();\n        \n        //vector to store possible index of w2 from rear to j so that from i of w1 a subsequence can match it \n\n        vector<int> v(m+1);\n        //last index will be out of bound for both therefor:\n        v[m]= n;\n\n        //remaining indexes:\n        int j=n-1; //last index of w2\n        for(int i=m-1; i>=0; i--){\n            if(j>=0 && w1[i] == w2[j]){\n                v[i]= j;\n                j--;\n            }\n            else{\n                v[i]= v[i+1];\n            }\n        }\n\n        j=0;\n        int swapIdx = -1;\n        for(int i=0; i<m; i++){\n            if(w1[i] == w2[j]){\n                j++;\n            }\n            else if(v[i+1] <= j+1){\n                swapIdx = j;\n                break;\n            }\n        }\n\n        j=0;\n        vector<int> ans;\n        \n        for(int i=0; i<m && j<n; i++){\n            if(j== swapIdx || w1[i]==w2[j]){\n                ans.push_back(i);\n                j++;\n            }\n        }\n\n        return (ans.size()<n ? vector<int>(0) : ans ) ;\n\n    }\n};\n\n```
['Two Pointers', 'Dynamic Programming', 'C++']