Lexicographically Smallest Valid Sequence
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```python []\nclass Solution(object):\n    def validSequence(self, word1, word2):\n        """\n        :type word1: str\n        :type word2: str\n        :rtype: List[int]\n        """\n        n = len(word2)\n        last = [-1] * n\n        j = n - 1\n        \n        # Find the last occurrence of each character in word2 within word1\n        for i in reversed(range(len(word1))): \n            if j >= 0 and word1[i] == word2[j]: \n                last[j] = i \n                j -= 1\n        \n        j = 0  # pointer for word2\n        cnt = 0  # track if one mismatch is allowed\n        ans = []\n        \n        # Iterate over word1 to find the lexicographically smallest sequence\n        for i in range(len(word1)):\n            if j < n:  # make sure we are within word2 bounds\n                if word1[i] == word2[j] or cnt == 0 and (j == n-1 or i + 1 <= last[j + 1]): \n                    if word1[i] != word2[j]:  # mismatch allowed once\n                        cnt = 1\n                    ans.append(i)  # add current index to result\n                    j += 1\n        \n        # If we successfully matched all of word2, return the result, otherwise return empty list\n        return ans if j == n else []\n\n```
['Python']