O(N) Two-pointers and improved Two-pass solution
Intuition\nTook me a while to figure out the naive approach. Tried DP / backtracking initially with no luck and TLE.\nThe idea is to check only for the matches 
# Intuition\nTook me a while to figure out the naive approach. Tried DP / backtracking initially with no luck and TLE.\nThe idea is to check only for the matches w/o the different char. \n\n# Approach #1 - Two-pointers\n## Warn - this gives TLE now as Leetcode updated the TCs\nOn each step we skip all the matching chars so far, then try to find the remaining part of word2 starting with current index $$i$$ in word1. If we can - we consider $$word1.charAt(i)$$ to be a different char, memorize the index i to the array and it is always the lixocographically smallest array.\nIf we can\'t - we go and find the j\'th word2 letter in word1, skip it and try again.\n\n# Complexity\n- Time complexity:\nMin - $$O(N + M)$$\nMax - $$O(N * M)$$\n\n- Space complexity:\n$$O(1)$$\n\n# Code\n\n```java []\nclass Solution {\n    public int[] validSequence(String word1, String word2) {\n        int i = 0, j = 0;\n        int[] res = new int[word2.length()];\n        while (i < word1.length() && j < word2.length() && word1.charAt(i) == word2.charAt(j)) {\n            res[j++] = i++;\n        }\n        while (i < word1.length() && j < word2.length()) {\n            if (find(word1, word2, i + 1, j + 1, res)) {\n                res[j] = i;\n                return res;\n            }\n            while (i < word1.length() && j < word2.length()) {\n                if (word1.charAt(i) == word2.charAt(j)) {\n                    while (i < word1.length() && j < word2.length() && word1.charAt(i) == word2.charAt(j)) {\n                        res[j++] = i++;\n                    }\n                    break;\n                } else {\n                    i++;\n                }\n            }\n        }\n        if (j < word2.length()) {\n            return new int[]{};\n        }\n        return res;\n    }\n\n    static boolean find(String w1, String w2, int i, int j, int[] res) {\n        while (i < w1.length() && j < w2.length()) {\n            if (w1.charAt(i) == w2.charAt(j)) {\n                res[j++] = i++;\n            } else {\n                i++;\n            }\n        }\n        return j == w2.length();\n    }\n\n}\n```\n```C++ []\nclass Solution {\npublic:\n    vector<int> validSequence(string word1, string word2) {\n        int i = 0, j = 0;\n        vector<int> res(word2.length());\n\n        while (i < word1.length() && j < word2.length() &&\n               word1[i] == word2[j]) {\n            res[j++] = i++;\n        }\n\n        while (i < word1.length() && j < word2.length()) {\n            if (find(word1, word2, i + 1, j + 1, res)) {\n                res[j] = i;\n                return res;\n            }\n            while (i < word1.length() && j < word2.length()) {\n                if (word1[i] == word2[j]) {\n                    while (i < word1.length() && j < word2.length() &&\n                           word1[i] == word2[j]) {\n                        res[j++] = i++;\n                    }\n                    break;\n                } else {\n                    i++;\n                }\n            }\n        }\n\n        if (j < word2.length()) {\n            return {};\n        }\n        return res;\n    }\n\nprivate:\n    bool find(const string& w1, const string& w2, int i, int j,\n              vector<int>& res) {\n        while (i < w1.length() && j < w2.length()) {\n            if (w1[i] == w2[j]) {\n                res[j++] = i++;\n            } else {\n                i++;\n            }\n        }\n        return j == w2.length();\n    }\n};\n```\n```C []\n#include <stdlib.h>\n#include <string.h>\n\n/**\n * Note: The returned array must be malloced, assume caller calls free().\n */\nint* validSequence(char* word1, char* word2, int* returnSize) {\n    int len1 = strlen(word1), len2 = strlen(word2);\n    int i = 0, j = 0;\n    int* res = (int*)malloc(len2 * sizeof(int));\n    \n    *returnSize = 0;\n    \n    while (i < len1 && j < len2 && word1[i] == word2[j]) {\n        res[j++] = i++;\n    }\n    \n    while (i < len1 && j < len2) {\n        if (find(word1, word2, i + 1, j + 1, res, len1, len2)) {\n            res[j] = i;\n            *returnSize = len2; // Update returnSize to the size of res\n            return res;\n        }\n        while (i < len1 && j < len2) {\n            if (word1[i] == word2[j]) {\n                while (i < len1 && j < len2 && word1[i] == word2[j]) {\n                    res[j++] = i++;\n                }\n                break;\n            } else {\n                i++;\n            }\n        }\n    }\n    \n    if (j < len2) {\n        free(res);\n        *returnSize = 0;\n        return NULL;\n    }\n    \n    *returnSize = len2;\n    return res;\n}\n\nint find(char* w1, char* w2, int i, int j, int* res, int len1, int len2) {\n    while (i < len1 && j < len2) {\n        if (w1[i] == w2[j]) {\n            res[j++] = i++;\n        } else {\n            i++;\n        }\n    }\n    return j == len2;\n}\n```\n```python []\nclass Solution:\n    def validSequence(self, word1: str, word2: str) -> List[int]:\n        def find(w1: str, w2: str, i: int, j: int, res: List[int]) -> bool:\n            while i < len(w1) and j < len(w2):\n                if w1[i] == w2[j]:\n                    res[j] = i\n                    j += 1\n                    i += 1\n                else:\n                    i += 1\n            return j == len(w2)\n\n        i, j = 0, 0\n        res = [-1] * len(word2)\n\n        while i < len(word1) and j < len(word2) and word1[i] == word2[j]:\n            res[j] = i\n            i += 1\n            j += 1\n\n        while i < len(word1) and j < len(word2):\n            if find(word1, word2, i + 1, j + 1, res):\n                res[j] = i\n                return res\n            while i < len(word1) and j < len(word2):\n                if word1[i] == word2[j]:\n                    while i < len(word1) and j < len(word2) and word1[i] == word2[j]:\n                        res[j] = i\n                        i += 1\n                        j += 1\n                    break\n                else:\n                    i += 1\n\n        if j < len(word2):\n            return []\n\n        return res\n```\n``` javascript []\n/**\n * @param {string} word1\n * @param {string} word2\n * @return {number[]}\n */\nvar validSequence = function (word1, word2) {\n    var find = function (w1, w2, i, j, res) {\n        while (i < w1.length && j < w2.length) {\n            if (w1.charAt(i) === w2.charAt(j)) {\n                res[j++] = i++;\n            } else {\n                i++;\n            }\n        }\n        return j === w2.length;\n    };\n\n    let i = 0, j = 0;\n    let res = new Array(word2.length).fill(-1);\n\n    while (i < word1.length && j < word2.length && word1.charAt(i) === word2.charAt(j)) {\n        res[j++] = i++;\n    }\n\n    while (i < word1.length && j < word2.length) {\n        if (find(word1, word2, i + 1, j + 1, res)) {\n            res[j] = i;\n            return res;\n        }\n        while (i < word1.length && j < word2.length) {\n            if (word1.charAt(i) === word2.charAt(j)) {\n                while (i < word1.length && j < word2.length && word1.charAt(i) === word2.charAt(j)) {\n                    res[j++] = i++;\n                }\n                break;\n            } else {\n                i++;\n            }\n        }\n    }\n\n    if (j < word2.length) {\n        return [];\n    }\n\n    return res;\n};\n```\n```Go []\nfunc validSequence(word1 string, word2 string) []int {\n\tfind := func(w1, w2 string, i, j int, res []int) bool {\n\t\tfor i < len(w1) && j < len(w2) {\n\t\t\tif w1[i] == w2[j] {\n\t\t\t\tres[j] = i\n\t\t\t\tj++\n\t\t\t\ti++\n\t\t\t} else {\n\t\t\t\ti++\n\t\t\t}\n\t\t}\n\t\treturn j == len(w2)\n\t}\n\n\ti, j := 0, 0\n\tres := make([]int, len(word2))\n\tfor index := range res {\n\t\tres[index] = -1\n\t}\n\n\tfor i < len(word1) && j < len(word2) && word1[i] == word2[j] {\n\t\tres[j] = i\n\t\ti++\n\t\tj++\n\t}\n\n\tfor i < len(word1) && j < len(word2) {\n\t\tif find(word1, word2, i+1, j+1, res) {\n\t\t\tres[j] = i\n\t\t\treturn res\n\t\t}\n\t\tfor i < len(word1) && j < len(word2) {\n\t\t\tif word1[i] == word2[j] {\n\t\t\t\tfor i < len(word1) && j < len(word2) && word1[i] == word2[j] {\n\t\t\t\t\tres[j] = i\n\t\t\t\t\ti++\n\t\t\t\t\tj++\n\t\t\t\t}\n\t\t\t\tbreak\n\t\t\t} else {\n\t\t\t\ti++\n\t\t\t}\n\t\t}\n\t}\n\n\tif j < len(word2) {\n\t\treturn []int{}\n\t}\n\n\treturn res\n}\n```\n# Approach #2 - Two pass\nAfter Leetcode updated the TCs the approach above started to get TLE for some languages (still worked in Go the last time I checked), I had to reconsider it.\n\nI took the same initial idea but improved it with the prefix array. Suppose we\'re at an index $$i$$ in the first word and at an index $$j$$ in second. Now the question we want to answer is - do we have the remaining parts of word1 in the remaining suffix of word2? If we can - we can greedily fill our result, if not - fast skip to the next iteration. To facilitate it let\'s first walk ***right to left*** in both words and fill the prefix array which says \'at the index $$i$$ I have $$prefix[i]$$ matching characters to the end of word1\'. Then we can get rid of `find()` function in the approach above altogether!\n\n# Complexity\n- Time complexity:\n$$O(N)$$\n\n- Space complexity:\n$$O(N)$$ - Note we traded time for space in the second approach\n\n```java []\nclass Solution {\n    public int[] validSequence(String word1, String word2) {\n        byte[] b1 = word1.getBytes(), b2 = word2.getBytes();\n        int n1 = b1.length, n2 = b2.length;\n        int[] pref = new int[n1];\n        // right to left\n        for (int i = n1 - 1, j = n2 - 1; i >= 0; i--) {\n            if (i < n1 - 1) {\n                pref[i] = pref[i + 1];\n            }\n            if (j >= 0 && b1[i] == b2[j]) {\n                pref[i]++;\n                j--;\n            }\n        }\n        // left to right\n        int[] res = new int[n2];\n        int match = 0;\n        for (int i = 0, j = 0; i < n1 && j < n2; i++) {\n            if (b1[i] == b2[j]) {\n                res[j++] = i;\n                match++;\n            } else if (i < n1 - 1 && pref[i + 1] >= n2 - match - 1) {\n                // greedy fill remaining\n                res[j++] = i++;\n                while (j < n2) {\n                    if (b1[i] == b2[j]) {\n                        res[j++] = i;\n                    }\n                    i++;\n                }\n                return res;\n            }\n        }\n        // if we matched everything w/o greedy fill\n        if (match == n2) {\n            return res;\n        }\n        return new int[] {};\n    }\n}\n```\n```C++ []\nclass Solution {\npublic:\n    vector<int> validSequence(string word1, string word2) {\n        int n1 = word1.length(), n2 = word2.length();\n        vector<int> pref(n1, 0);\n\n        // right to left\n        for (int i = n1 - 1, j = n2 - 1; i >= 0; i--) {\n            if (i < n1 - 1) {\n                pref[i] = pref[i + 1];\n            }\n            if (j >= 0 && word1[i] == word2[j]) {\n                pref[i]++;\n                j--;\n            }\n        }\n\n        // left to right\n        vector<int> res(n2, -1);\n        int match = 0;\n        for (int i = 0, j = 0; i < n1 && j < n2; i++) {\n            if (word1[i] == word2[j]) {\n                res[j++] = i;\n                match++;\n            } else if (i < n1 - 1 && pref[i + 1] >= n2 - match - 1) {\n                // Greedy fill remaining\n                res[j++] = i++;\n                while (j < n2) {\n                    if (word1[i] == word2[j]) {\n                        res[j++] = i;\n                    }\n                    i++;\n                }\n                return res;\n            }\n        }\n\n        if (match == n2) {\n            return res;\n        }\n        return vector<int>();\n    }\n};\n```\n```C []\n#include <stdlib.h>\n#include <string.h>\n\n/**\n * Note: The returned array must be malloced, assume caller calls free().\n */\nint* validSequence(char* word1, char* word2, int* returnSize) {\n    int n1 = strlen(word1), n2 = strlen(word2);\n    int* pref = (int*)malloc(n1 * sizeof(int));\n    memset(pref, 0, n1 * sizeof(int));\n\n    // right to left\n    for (int i = n1 - 1, j = n2 - 1; i >= 0; i--) {\n        if (i < n1 - 1) {\n            pref[i] = pref[i + 1];\n        }\n        if (j >= 0 && word1[i] == word2[j]) {\n            pref[i]++;\n            j--;\n        }\n    }\n\n    // left to right\n    int* res = (int*)malloc(n2 * sizeof(int));\n    int match = 0;\n    *returnSize = 0;\n\n    for (int i = 0, j = 0; i < n1 && j < n2; i++) {\n        if (word1[i] == word2[j]) {\n            res[j++] = i;\n            match++;\n        } else if (i < n1 - 1 && pref[i + 1] >= n2 - match - 1) {\n            // Greedy fill remaining\n            res[j++] = i++;\n            while (j < n2) {\n                if (word1[i] == word2[j]) {\n                    res[j++] = i;\n                }\n                i++;\n            }\n            *returnSize = n2;\n            free(pref);\n            return res;\n        }\n    }\n\n    if (match == n2) {\n        *returnSize = n2;\n        free(pref);\n        return res;\n    }\n\n    free(pref);\n    free(res);\n    *returnSize = 0;\n    return NULL;\n}\n```\n```python []\nfrom typing import List\n\nclass Solution:\n    def validSequence(self, word1: str, word2: str) -> List[int]:\n        n1, n2 = len(word1), len(word2)\n        pref = [0] * n1\n\n        # right to left\n        j = n2 - 1\n        for i in range(n1 - 1, -1, -1):\n            if i < n1 - 1:\n                pref[i] = pref[i + 1]\n            if j >= 0 and word1[i] == word2[j]:\n                pref[i] += 1\n                j -= 1\n\n        # left to right\n        res = [-1] * n2\n        match = 0\n        i, j = 0, 0\n        while i < n1 and j < n2:\n            if word1[i] == word2[j]:\n                res[j] = i\n                j += 1\n                match += 1\n            elif i < n1 - 1 and pref[i + 1] >= n2 - match - 1:\n                res[j] = i\n                j += 1\n                i += 1\n                while j < n2 and i < n1:\n                    if word1[i] == word2[j]:\n                        res[j] = i\n                        j += 1\n                    i += 1\n                return res\n\n            i += 1\n\n        if match == n2:\n            return res\n        return []\n```\n``` javascript []\n/**\n * @param {string} word1\n * @param {string} word2\n * @return {number[]}\n */\nvar validSequence = function (word1, word2) {\n    const n1 = word1.length, n2 = word2.length;\n    const pref = new Array(n1).fill(0);\n\n    // right to left\n    let j = n2 - 1;\n    for (let i = n1 - 1; i >= 0; i--) {\n        if (i < n1 - 1) {\n            pref[i] = pref[i + 1];\n        }\n        if (j >= 0 && word1[i] === word2[j]) {\n            pref[i]++;\n            j--;\n        }\n    }\n\n    // left to right\n    const res = new Array(n2).fill(-1);\n    let match = 0;\n    let i = 0;\n    j = 0;\n\n    while (i < n1 && j < n2) {\n        if (word1[i] === word2[j]) {\n            res[j] = i;\n            j++;\n            match++;\n        } else if (i < n1 - 1 && pref[i + 1] >= n2 - match - 1) {\n            res[j] = i;\n            j++;\n            i++;\n            while (j < n2 && i < n1) {\n                if (word1[i] === word2[j]) {\n                    res[j] = i;\n                    j++;\n                }\n                i++;\n            }\n            return res;\n        }\n        i++;\n    }\n\n    if (match === n2) {\n        return res;\n    }\n\n    return [];\n};\n```\n```Go []\nfunc validSequence(word1 string, word2 string) []int {\n\tn1, n2 := len(word1), len(word2)\n\tpref := make([]int, n1)\n\n\t// right to left\n\tj := n2 - 1\n\tfor i := n1 - 1; i >= 0; i-- {\n\t\tif i < n1-1 {\n\t\t\tpref[i] = pref[i+1]\n\t\t}\n\t\tif j >= 0 && word1[i] == word2[j] {\n\t\t\tpref[i]++\n\t\t\tj--\n\t\t}\n\t}\n\n\t// left to right\n\tres := make([]int, n2)\n\tmatch := 0\n\ti, j := 0, 0\n\tfor i < n1 && j < n2 {\n\t\tif word1[i] == word2[j] {\n\t\t\tres[j] = i\n\t\t\tj++\n\t\t\tmatch++\n\t\t} else if i < n1-1 && pref[i+1] >= n2-match-1 {\n\t\t\tres[j] = i\n\t\t\tj++\n\t\t\ti++\n\t\t\tfor j < n2 && i < n1 {\n\t\t\t\tif word1[i] == word2[j] {\n\t\t\t\t\tres[j] = i\n\t\t\t\t\tj++\n\t\t\t\t}\n\t\t\t\ti++\n\t\t\t}\n\t\t\treturn res\n\t\t}\n\t\ti++\n\t}\n\n\tif match == n2 {\n\t\treturn res\n\t}\n\n\treturn []int{}\n}\n```
['Two Pointers', 'C', 'Sliding Window', 'Prefix Sum', 'Python', 'C++', 'Java', 'Go', 'Python3', 'JavaScript']