| Beats 100%✅ | Python | 2 Pointer Approach | Suffix Array |
\n# Approach\n Describe your approach to solving the problem. \n\nThe goal is to determine if word2 can be formed as a subsequence of word1 by allowing one mism
\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\nThe goal is to determine if word2 can be formed as a subsequence of word1 by allowing one mismatch or skipped character from word1. \n\nstep 1:\nThe algorithm first computes an array maxSuff that stores the maximum suffix match lengths for word1. This helps to decide whether the remaining part of word2 can still be matched after a mismatch. \nstep 2:\nAfter constructing this helper array, it iterates over both strings, trying to match characters. If a mismatch occurs, the algorithm checks if skipping a character from word1 will still allow the rest of word2 to match. If it can, the algorithm proceeds with one mismatch allowed. The answer will be the list of indices in word1 that match word2, or an empty list if no valid subsequence is found.\n\n\n\n# Complexity\n- Time complexity: O(m + n)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n\n- Space complexity: O(m)\n\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        \n        # Initialize pointers at the end of both words\n        i, j = len(word1) - 1, len(word2) - 1\n        ans = []  # List to store matching indices from word1\n        oneChance = True  # Allows one mismatch between the two words\n        maxSuff = [0] * len(word1)  # Array to track maximum suffix match lengths\n\n        # Step 1: Build the maxSuff array to track possible suffix matches##########################\n        while i >= 0 and j >= 0:\n            if word1[i] == word2[j]:\n                # If the characters match, record the match length\n                maxSuff[i] = len(word2) - j\n                j -= 1  # Move to the previous character in word2\n            i -= 1  # Move to the previous character in word1\n        \n        # Propagate the maximum suffix match length backwards\n        for i in range(len(word1) - 2, -1, -1):\n            maxSuff[i] = max(maxSuff[i], maxSuff[i + 1])\n\n        # Reset pointers for the next part of the algorithm\n        i,j = 0,0\n\n        # Step 2: Attempt to match word2 as a subsequence of word1####################################\n        while i < len(word1) and j < len(word2):\n            if word1[i] == word2[j]:\n                # If characters match, store the index and move both pointers\n                ans.append(i)\n                i += 1\n                j += 1\n            else:\n                # If there is a mismatch, calculate the remaining characters in word2\n                remLen = len(word2) - j - 1\n\n                # Check if we can skip one character in word1 and still match the rest of word2\n                if i + 1 < len(word1) and maxSuff[i + 1] >= remLen and oneChance:\n                    ans.append(i)  # Store the mismatch index\n                    i += 1  # Skip this character in word1\n                    j += 1  # Move to the next character in word2\n                    oneChance = False  # Use the one allowed mismatch\n                else:\n                    i += 1  # Otherwise, move to the next character in word1\n\n            # Break early if the remaining characters in word1 are insufficient to match word2\n            if len(word1) - i < len(word2) - j:\n                break\n\n        # If we matched the entire word2, return the indices, otherwise return an empty list\n        return ans if len(ans) == len(word2) else []\n```
['Two Pointers', 'Suffix Array', 'Python3']