C++ Easy Greedy with Tutorial 👌
Tutorial\n1. Save the last seen position of each character of word2, by iterating over word1 backwards.\n2. Use two pointers for matching letters from word1 and
# Tutorial\n1. Save the last seen position of each character of word2, by iterating over word1 backwards.\n2. Use two pointers for matching letters from word1 and word2: we must accept a "coin" when the char match is not equal between them. The coin is accepted if the word2 pointer is in its last position, or if the next letter in word2 was last seen ahead of the current pointer of word2.\n\nI hope I could help! \uD83D\uDE0A\n\n# Complexity\n- Time complexity:\nO(M + N) = O(M)\n\n- Space complexity:\nO(2*N) = O(N)\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    vector<int> validSequence(string word1, string word2) {\n        int m = word1.size(), n = word2.size();\n        vector<int> lastSeen(n, -1);\n        vector<int> res;\n\n\n        for (int i = m - 1, j = n - 1; i >= 0; i--) {\n            if (j >= 0 && word1[i] == word2[j]) {\n                lastSeen[j] = i;\n                j--;\n            }\n        }\n\n        int matchPos = 0, coin = 0;\n        for (int i = 0; i < m; i++) {\n            if (matchPos < n) {\n                bool letterMatch = word1[i] == word2[matchPos];\n                if (letterMatch || (!coin && (matchPos == n - 1 || (i + 1 <= lastSeen[matchPos + 1])))) {\n                    if (!letterMatch)\n                        coin = 1;\n                    res.push_back(i);\n                    matchPos++;\n                }\n            }\n        }\n\n        return matchPos == n ? res : vector<int>();\n    }\n};\n```\n\n![image.png](https://assets.leetcode.com/users/images/f08f089f-f322-47ff-a6bb-d60948a469cb_1727554038.2704194.png)\n
['C++']