[Python3] Greedy + Two Pointers - Detailed Explanation
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n1. Initialization:\n\n-
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n**1. Initialization:**\n\n- `m` and `n` store the lengths of `word1` and `word2`, respectively.\n- `last` is an array to store the last index in `word1` where a character matches a corresponding character in `word2`.\n- `j` is initialized to `n - 1` to start from the end of `word2`.\n- `res` is a list to store the indices of characters to be removed.\n- `skip` is initialized to 0 to track whether a character can be skipped.\n\n**2. Find Last Occurrences:**\n\n- The loop iterates backward through `word1`.\n- If a character in `word1` matches the current character in `word2`, the corresponding index in `last` is updated.\n- `j` is decremented to move to the previous character in `word2`.\n\n**3. Build the Result:**\n\n- The loop iterates over each character in `word1`.\n- If `j` is `n`, it means all characters in `word2` have been matched, and the loop breaks.\n- If the current character in `word1` matches the current character in `word2` or if `skip` is 0 and the current character in `word1` can be skipped (based on the `last` array), the character is added to `res`.\n- `skip` is incremented if the current character in `word1` doesn\'t match the current character in `word2` and cannot be skipped.\n- `j` is incremented to move to the next character in `word2`.\n\n**4. Return Result:**\n\n- If `j` is `n` after the loop, it means all characters in `word2` were matched, and the `res` list contains the indices of characters to be removed.\n- Otherwise, it means `word2` cannot be formed from `word1`, and an empty list is returned.\n\nIn summary, the code efficiently determines if `word2` can be formed from `word1` by removing characters and returns the indices of those characters if possible. It utilizes a `last` array to track the last occurrences of characters in `word1` that match characters in `word2` and a `skip` variable to handle cases where a character can be skipped.\n\n# Complexity\n- Time complexity: $$O(W1 + W2)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(W2)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```python3 []\nclass Solution:\n    def validSequence(self, word1: str, word2: str) -> List[int]:\n        w1, w2 = len(word1), len(word2)\n        last = [-1 for _ in range(w2)]\n        j = w2 - 1\n        for i in range(w1 - 1, -1, -1):\n            if j >= 0 and word1[i] == word2[j]:\n                last[j] = i\n                j -= 1\n        res = []\n        skip = j = 0\n        for i, c in enumerate(word1):\n            if j == w2: break\n            if word1[i] == word2[j] or skip == 0 and (j == w2 - 1 or i < last[j + 1]):\n                skip += word1[i] != word2[j]\n                res.append(i)\n                j += 1\n        return res if j == w2 else []\n```
['Two Pointers', 'String', 'Greedy', 'Python3']