Python greedy solution 763 ms
Complexity\n- Time complexity:\nO(len(word1))\n\n- Space complexity:\nO(len(word2))\n\n# Code\npython3 []\nclass Solution:\n    def validSequence(self, word1: s
Complexity\n- Time complexity:\nO(len(word1))\n\n- Space complexity:\nO(len(word2))\n\n# Code\n```python3 []\nclass Solution:\n    def validSequence(self, word1: str, word2: str) -> List[int]:\n        word1_len = len(word1)\n        word2_len = len(word2)\n        suffix = [-1] * (word2_len + 1)\n        suffix[-1] = word1_len\n        have_pos = word1_len - 1\n        for need_pos in reversed(range(word2_len)):\n            need = word2[need_pos]\n            while have_pos >= 0 and word1[have_pos] != need:\n                have_pos -= 1\n\n            if not have_pos >= 0:\n                break\n\n            suffix[need_pos] = have_pos\n            have_pos -= 1\n\n        result = []\n        word2_pos = 0\n        can_mutate = True\n\n        for word1_pos, letter in enumerate(word1):            \n            if letter == word2[word2_pos]:\n                # always take matches\n                result.append(word1_pos)                \n                word2_pos += 1\n            elif can_mutate and word1_pos + 1 <= suffix[word2_pos + 1]:\n                # can build everything from this position\n                result.append(word1_pos)  # mutate once\n                word2_pos += 1\n                can_mutate = False\n\n            if word1_len - word1_pos < word2_len - word2_pos:\n                return []\n                \n            if word2_pos == word2_len:\n                return result\n\n```
['Two Pointers', 'Greedy', 'Python3']