Beats 100% || easy approach || linear time complexity
Complexity\n- Time complexity:O(n)\n Add your time complexity here, e.g. O(n) \n\n- Space complexity:O(n)\n Add your space complexity here, e.g. O(n) \n\n# Code
# Complexity\n- Time complexity:O(n)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:O(n)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```python []\nclass Solution(object):\n    def __init__(self):\n        self.res = []\n\n    def validSequence(self, word1, word2):\n        """\n        :type word1: str\n        :type word2: str\n        :rtype: List[int]\n        """\n\n        dp = [-1]*len(word2)\n        j = len(word2)-1\n        for i in range(len(word1)-1, -1, -1):\n            if word1[i] == word2[j]:\n                dp[j] = i\n                j-=1\n            if j < 0:\n                break\n        \n        j = 0\n        ans = []\n        flag = True\n        for i in range(len(word1)):\n            if word1[i] == word2[j] or (flag and(j == len(word2)-1 or i+1 <= dp[j+1])):\n                if word1[i] != word2[j]:\n                    flag = False\n                \n                j+=1\n                ans.append(i)\n            \n            if j >= len(word2):\n                break\n        \n        if len(ans) == len(word2):\n            return ans\n        ans = []\n        return ans\n\n                \n```
['Python']