Typescript Approach [O(n) Time/Space]
Intuition\nThe task is to find a valid sequence of indices from word1 such that it can match word2 by changing at most one character. To achieve this, we look f
# Intuition\nThe task is to find a valid sequence of indices from `word1` such that it can match `word2` by changing at most one character. To achieve this, we look for a subsequence in `word1` that matches `word2` either exactly or with a single modification.\n\nThe goal is to first check from the end of `word1` if the remaining characters can still match the remaining part of `word2`. This helps us decide if we can afford a mismatch while still being able to complete the sequence. The covers array helps track this information.\n\n# Approach\n1. Calculate the covers array: `covers[i]` stores how many characters of `word2` (from `j` onwards) can still be matched starting from index `i` of `word1`. It is built by scanning `word1` from right to left. If `word1[i] == word2[j]`, we increment `covers[i]` based on the subsequent positions. This allows us to know, for any index `i`, whether the remaining portion of `word2` can still be matched if we skip a character in `word1`.\n2. First Pass to Attempt a Match: We attempt to match the characters of `word2` from left to right with `word1`. If a mismatch occurs, we check if we can afford this mismatch using the `covers` array (i.e., whether the remaining part of `word1` can still cover the rest of `word2`). If a mismatch is allowed, we mark that spot (`victory`) and try to complete the sequence from there.\n3. Second Pass After a Mismatch: If the sequence was interrupted by a mismatch, we attempt to finish matching the remaining characters of `word2` starting from the `victory` index. This second pass ensures that we can complete the sequence even after one character was mismatched.\n4. Result Check: If the `result` size matches the length of `word2`, we return the indices. If we couldn\u2019t complete the sequence, return an empty array.\n\n# Complexity\n- Time complexity:\nThe total time complexity is $O(n)$, where $n$ is the length of `word1`.\n\n- Space complexity:\n$O(n)$, due to the `covers` array.\n\n# Code\n```typescript []\nfunction validSequence(word1: string, word2: string): number[] {\n    const n = word1.length\n    const m = word2.length\n    const covers: number[] = new Array(n).fill(0)\n    let j = m - 1\n\n    for (let i = n - 1; i >= 0; i--) {\n        if (j >= 0 && word1[i] === word2[j]) {\n            covers[i] = i === n - 1 ? 1 : covers[i + 1] + 1\n            j--\n        } else {\n            covers[i] = i === n - 1 ? 0 : covers[i + 1]\n        }\n    }\n\n    j = 0\n    const result: number[] = []\n    let victory = -1\n\n    for (let i = 0; i < n; i++) {\n        if (word1[i] === word2[j]) {\n            result.push(i)\n            j++\n            if (j === m) {\n                break\n            }\n        } else {\n            if ((i === n - 1 ? 0 : covers[i + 1]) >= m - j - 1) {\n                result.push(i)\n                j++\n                victory = i + 1\n                break\n            }\n        }\n    }\n\n    if (result.length === m) {\n        return result\n    }\n\n    if (victory === -1) {\n        return []\n    }\n\n    for (let i = victory; i < n; i++) {\n        if (word1[i] === word2[j]) {\n            result.push(i)\n            j++\n        }\n        if (j === m) {\n            break\n        }\n    }\n\n    return result.length === m ? result : []\n}\n```
['TypeScript', 'JavaScript']