Easy approach
\n\n# Approach\nWhen you encounter a mismatch, you want to know whether skipping that mismatch will still allow you to match the remaining characters of s2 from
\n\n# Approach\nWhen you encounter a mismatch, you want to know whether skipping that mismatch will still allow you to match the remaining characters of s2 from s1.\nTo help with this, we can precompute a dp array where dp[i] tells us how many characters of s2 can still be matched starting from position i in s1.\nThis dp array is computed by working backward through s1, checking how much of s2 can still be matched from each position.\n\n# Complexity\n- Time complexity:\n   $$O(n)$$ \n- Space complexity:\n$$O(n)$$ \n\n# Code\n```python3 []\nclass Solution:\n    def validSequence(self, s1: str, s2: str) -> list[int]:\n        n = len(s1)\n        m = len(s2)\n        res = []\n        dp = [0] * (n + 1)\n        op = True\n        cur = m - 1\n        \n        for i in range(n - 1, -1, -1):\n            dp[i] = dp[i + 1]\n            if cur >= 0 and s1[i] == s2[cur]:\n                cur -= 1\n                dp[i] += 1\n        j = 0 \n        for i in range(n):\n            if j >= m:\n                break\n            if s1[i] == s2[j]:\n                res.append(i)\n                j += 1\n            elif dp[i + 1] + 1 > m - j - 1 and op:\n\n                res.append(i)\n                op = False\n                j += 1\n        \n        if len(res) != m:\n            return []\n        \n        return res\n\n```
['Python3']