C++ O(m) TC & O(n) SC, 100% both
Idea\nBasically do greedy search twice: one backward and one forward. \n\nIn the first search, for each second part of word2, find and record the last places in
# Idea\nBasically do greedy search twice: one backward and one forward. \n\nIn the first search, for each second part of word2, find and record the last places in word1, from where that second part of word2 is a subsequence of the second part of word1. \n\nIn the second search, the recorded places will tell us where is the first possible place we can use a wrong character. \n\nMore specific:\nThe j-th charcter can be wrong if all previous j - 1 matched charcters are correct, and remain characters in word2 is a subsequence of remain characters in word1.\nCombined with the recored places we found in first search, that is: \n```\nmatched_place[j-1] + 1 < recorded_place[j+1]\n```\n\n\nBoth search can be done with simple pointer method.\n\n# Complexity\n- Time complexity:\nO(m + n) = O(m) // since n < m\n\n- Space complexity:\nO(n)\n\nwhere m = word1.length() n = word2.length()\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    vector<int> validSequence(string word1, string word2) {\n        if (word2.length() == 1) return {0};\n        int n1 = word1.length(), n2 = word2.length();\n        vector<int> p(word2.size(), -1);\n        vector<int> r;\n        int i = n1 - 1, j = n2 - 1;\n        while (i >= 0 && j >= 0) {\n            if (word1[i] == word2[j]) p[j--] = i;\n            i--;\n        }\n        i = 0;\n        j = 0;\n        \n        bool t = false;\n        if (0 < p[1] && word1[0] != word2[0]) {\n            t = true;\n            r.push_back(i++);\n            j++;\n        }\n        while (i < n1 && j < n2) {\n            if(word1[i]!=word2[j]){\n                if(!t && (j == n2 - 1 || i < p[j + 1] )){\n                    t = true;\n                    r.push_back(i);\n                    j++;\n                } \n            } else {\n                r.push_back(i);\n                j++;\n            } \n            i++;\n        }\n        if (j == n2) return r;\n        return {};\n    }\n};\n//Charl Ep\n```
['C++']