[Java/C++/Python] Find Smallest Skip Index
Explanation\nFind the last chance of word1[i] to match word2[j].\nIf we miss word1[i], where i = last[j],\nwe can\'t find almost eqaul string.\n\nItearate each 
# **Explanation**\nFind the `last` chance of `word1[i]` to match `word2[j]`.\nIf we miss `word1[i]`, where `i = last[j]`,\nwe can\'t find almost eqaul string.\n\nItearate each character in `word1`,\nIf it equals to `word2[j]`, we greedliy take it.\nIf it doesn\'t, we try to skip `word2[j]` by checking `i < last[j + 1]`.\n\nThese two cases will make the `res` as smallest as possible.\n\nFinally return the `res` if we found the almoast eqaul string.\n\n<br>\n\n# **Complexity**\nTime `O(n + m)`\nSpace `O(m)`\n<br>\n\n**Java**\n```java\n    public int[] validSequence(String word1, String word2) {\n        int n = word1.length(), m = word2.length();\n        int[] last = new int[m];\n        Arrays.fill(last, -1);\n        for (int i = n - 1, j = m - 1; i >= 0; --i)\n            if (j >= 0 && word1.charAt(i) == word2.charAt(j))\n                last[j--] = i;\n        int j = 0, res[] = new int[m], skip = 0;\n        for (int i = 0; i < n && j < m; ++i) {\n            if (word1.charAt(i) == word2.charAt(j) || (skip == 0 && (j == m - 1 || i < last[j + 1]))) {\n                res[j] = i;\n                skip += (word1.charAt(i) != word2.charAt(j)) ? 1 : 0;\n                j++;\n            }\n        }\n        return j == m ? res : new int[0];\n    }\n```\n\n**C++**\n```cpp\n    vector<int> validSequence(string word1, string word2) {\n        int n = word1.size(), m = word2.size(), skip = 0;\n        vector<int> last(m, -1);\n        for (int i = n - 1, j = m - 1; i >= 0; --i)\n            if (j >= 0 && word1[i] == word2[j])\n                last[j--] = i;\n        vector<int> res;\n        for (int i = 0, j = 0; i < n && j < m; ++i) {\n            if (word1[i] == word2[j] || (skip == 0 && (j == m - 1 || i < last[j + 1]))) {\n                res.push_back(i);\n                skip += (word1[i] != word2[j++]);\n            }\n        }\n        return res.size() == m ? res : vector<int>();\n    }\n```\n\n**Python**\n```py\n    def validSequence(self, word1: str, word2: str) -> List[int]:\n        n, m = len(word1), len(word2)\n        last = [-1] * m\n        j = m - 1\n        for i in range(n - 1, -1, -1):\n            if j >= 0 and word1[i] == word2[j]:\n                last[j] = i\n                j -= 1\n        res = []\n        skip = j = 0\n        for i, c in enumerate(word1):\n            if j == m: break\n            if word1[i] == word2[j] or skip == 0 and (j == m - 1 or i < last[j + 1]):\n                skip += word1[i] != word2[j]\n                res.append(i)\n                j += 1\n        return res if j == m else []\n```\n
['C', 'Python', 'Java']