Python O(N) - use suffix_match array to determine if a letter can be skipped
Intuition\nWe can create an array called suffix_match with the same length as word1. This array will store, for each index in word1, the length of the longest s
# Intuition\nWe can create an array called `suffix_match` with the same length as `word1`. This array will store, for each index in `word1`, the length of the longest suffix we can match in `word2` starting at that index. This is built from right to left, matching right-most characters of `word2` with right-most characters of `word1`.\n\nWe then build the solution from left to right using `word1`. For each matching letter between `word1` and `word2`, we add its index to a list.\n\nThe key step occurs when we encounter a non-matching pair of letters. At this point, we check if we can use our single skip by checking if we can match enough remaining letters starting from the next index in the `suffix_match` array.\n\nFor example, for an input like\n```\nword1 = "xxxabzzzdefxxx" \nword2 = "abcdef"\n```\n\nThe `suffix_match` array would look like\n```\nword1 =        x x x a b z z z d e  f  x  x  x\nsuffix_match = 3 3 3 3 3 3 3 3 3 2  1  0  0  0 \nindices =      0 1 2 3 4 5 6 7 8 9 10 11 12 13\n```\nThis is because `f`, `e`, and `d` get matched as we traverse from right to left, each increasing the value by 1, and then a match for `c` is never found.\n\nSo searching from left to right, we compare `x` and `a`. Since they don\'t match, we check if we can use our skip on `x`. Since there are 5 characters left (`bcdef`) and the `suffix_match[0]` says we can only match 3 (3 < 5), we can\'t skip `x`. The same thing happens for the other two `x`s. \n\nWhen we reach `a`, we find the first match and add index 3 to our answer. Then `b` also matches and our current answer is [3, 4]. When we reach `z`, it doesn\'t match with `c`, so we check if we can use our skip. Since there are 4 letters left (`cdef`), if we use our skip on `c`, we would only have to match 3 characters (`def`), and since `suffix_match[5] == 3`, this means that we can skip `c` and still match the rest of the letters (`def`). So we add the current index to our answer ([3, 4, 5]), and since we`ve used our skip, we now look for actual matches.\n\nWe get to indices 8-10 where we find matches for `def`, and our answer becomes [3, 4, 5, 8, 9, 10]. Since we found matches for all the letters in word2, this is the answer.\n\nIf we never either find a letter that we can skip, or find perfect matches for each of the letters, then there is no answer and we return an empty array.\n\n# Approach\n1. Build the `suffix_match` array\n2. Start finding matching letters between `word1` and `word2` and add their indices to an array, searching from left to right\n    - For every pair of letters that don\'t match, use the `suffix_match` array to check if this letter can be skipped\n        - If it can be skipped, add that index to the array and break out of the loop\n        - If it can\'t continue to the next letter\n    - If a full match is found without skipping letters, return the answer early\n3. If the loop terminated early and it was determined that a letter could be skipped, then find the earliest occurrences for the remaining letters (which are guaranteed to exist)\n4. Return the answer\n\n# Complexity\n- Time complexity: $$O(N)$$\n\n- Space complexity: $$O(N)$$\n\n# Code\n```python3 []\nclass Solution:\n    def validSequence(self, wordA: str, wordB: str) -> List[int]:\n        A = len(wordA)\n        B = len(wordB)\n\n        # Construct the \'suffix_match\' array\n        # For every index i in \'suffix_match\', we can be sure that we can match\n        # the last \'suffix_match[i]\' chars of wordB if we start matching at index i\n        suffix_match = [0] * (A + 1)  # One extra slot at the end to avoid out-of-bounds\n        b = B - 1  # pointer for wordB chars, set to last character\n        for a in range(A - 1, -1, -1):\n            if b >= 0 and wordB[b] == wordA[a]:\n                suffix_match[a] = suffix_match[a + 1] + 1\n                b -= 1\n            else:\n                suffix_match[a] = suffix_match[a + 1]\n\n        # Try to create the answer by matching chars from left to right, and use suffix_match\n        # to see if we can skip a character and still find the answer\n        answer = []\n        a = b = 0\n        found = 0\n        starting_point = 0\n        for a in range(A):\n            if wordA[a] == wordB[b]:\n                answer.append(a)\n                found += 1\n                b += 1\n                if b == B:  # If we find a full match early, return it\n                    return answer\n            else:\n                if (found + 1 + suffix_match[a + 1]) >= B:  # If we can skip current char and still match the rest\n                    answer.append(a)  # This will be the skipped char\n                    found += 1\n                    starting_point = a + 1\n                    b += 1\n                    break\n\n        # If we found all the letters without skipping, we can return\n        if found == B:\n            return answer\n\n        # If starting_point didn\'t change, it determined that no chars could be skipped\n        if starting_point == 0:\n            return []\n\n        # Starting from \'starting_point\', we know we can match the rest of the letters if we got this far\n        # So this loop just finds the earliest indices for those letters\n        for a in range(starting_point, A):\n            if wordA[a] == wordB[b]:\n                answer.append(a)\n                b += 1\n                if b == B:\n                    break\n\n        return answer\n\n```\n\n\n# Test cases\n```\n"xxabzzzdefxx"\n"abcdef"\n\n"axbc"\n"abc"\n\n"xxxabcxxxxx"\n"abc"\n\n"xyzabqdefxyz"\n"abcdef"\n\n"abcxxxxx"\n"abc"\n\n"bacdc"\n"abc"\n\n"aaaaaa"\n"aaabc"\n\n"xxyxxwxxxz"\n"yvz"\n\n"cbbcbcccbbbbb"\n"bb"\n\n"cbbcbcbcbc"\n"b"\n```
['Python', 'Python3']