Greedy, Prefix-sum-like Precomputation | O(𝑛), O(𝑛) | 60.60%, 50.48%
Intuition\n Describe your first thoughts on how to solve this problem. \nAs we are finding the lexicographically smallest valid sequence, we can compare both st
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nAs we are finding the lexicographically smallest valid sequence, we can compare both strings from left to right where in the left-to-right traversal order **any first matches will surely go into building the sequence**. We are however allowed one mismatch for the sequence to still be valid. As such, when we encounter one, we have to **determine if the mismatch can be used** in the sequence by **seeing if the rest of the string will still have enough matches** to be valid. We can do this by **precomputing the number of matching characters from right to left** in a prefix-sum-like manner (or suffix in this case).\n\nOur approach combines <ins>greedy selection with precomputation</ins> of matching characters in a <ins>prefix-sum-like logic</ins> (but from the right), to pick valid characters as early as possible. <ins>Two pointers</ins> are used to compare characters in the two words for matches.\n# Approach\n<!-- Describe your approach to solving the problem. -->\n- By traversing from right to left, precompute an array `right_matches` that stores the number of matching characters between the suffix of `word1` (starting from each index) and the suffix of `word2`.\n- Traverse `word1` from left to right to greedily select the smallest valid sequence of indices.\n    - If the current character matches the current character in `word2`, add the index to the output.\n    - If there is a mismatch, check if enough matches remain to the right to still construct `word2` with one mismatch.\n- If a valid sequence of size `len(word2)` is found, return it. Otherwise, return an empty array.\n# Complexity\n*where $n=n_1$ and $n_1>=n_2$,\nwhere $n_1$ and $n_2$ are the lengths of strings `word1` and `word2` respectively.*\n- **Time complexity: O(\uD835\uDC5B)**\nDue to linear pass of `word1` first to compute the `right_matches` array, and then second to construct the `output`sequence.\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n- **Space complexity: O(\uD835\uDC5B)**\nDue to storing the `right_matches` array, and the `output` sequence.\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n| Runtime    | Memory |\n| -------- | ------- |\n| **822** ms &#124; beats **60.60%** | **46.51** MB &#124; beats **50.48%**|\n```python3 []\nclass Solution:\n    def validSequence(self, word1: str, word2: str) -> List[int]:\n        n1, n2 = len(word1), len(word2)\n\n        right_matches = [0] * (n1) # right_matches[i] = no. of matched characters (from the right) of word2 from index i+1 in word1\n\n        j = n2-1 #pointer for word2 from right\n        matches = 0 #counter for word2 matches from the right\n        for i in range(n1-1,0,-1):\n            if matches == n2:\n                pass\n            elif word1[i] == word2[j]:\n                j -= 1\n                matches += 1\n            right_matches[i-1] = matches\n        # print("right_matches", right_matches)\n        output = []\n        j = 0 #reset j pointer to left of word2\n        mismatch = 1 #allow 1 mismatch\n        for i in range(n1):\n            if word1[i] == word2[j]:\n                output.append(i)\n                j += 1\n            else:\n                if mismatch > 0:\n                    if right_matches[i] >= n2 - len(output) -1 : # enough matches to its right, can use mismatch here\n                        output.append(i)\n                        mismatch -= 1\n                        j += 1\n            if j == n2:\n                return output\n        return []\n```\n# Detailed Approach\n1. Initialize `right_matches`:\n    - `right_matches[i]` stores the number of matching characters (from `i+1` to end of `word1`) with `word2` from the right side.\n    - This helps determine whether a mismatch can be used at the current index, since the remaining part of `word1` must still contain enough matching characters to complete `word2`.\n2. Precompute `right_matches`:\n    - Traverse `word1` from right to left, comparing characters with `word2`.\n    - Keep track of how many characters from word2 (from its right) match with the current part of `word1`.\n    - Store these counts in the `right_matches` array to use later when evaluating mismatches.\n3. Build sequence of indices:\n    - Traverse `word1` from left to right.\n    - For each index:\n        - If the character matches the next character in `word2`, add the index to the output.\n        - If there\u2019s a mismatch (and if a mismatch has not been used to build the sequence), check `right_matches[i]` to see whether the remaining part of `word1` still has enough matches to finish constructing `word2`.\n            - If yes, use this index as the one allowed mismatch and continue.\n    - Return the sequence of indices if `word2` is fully constructed (early exit), otherwise, return an empty array.\n\n# Detailed Complexity Breakdown\n*where $n=n_1$ and $n_1>=n_2$,\nwhere $n_1$ and $n_2$ are the lengths of strings `word1` and `word2` respectively.*\n### Time Complexity: $O(\uD835\uDC5B)$\n1. Initialize `right_matches`:\n    - This array of size $n_1$ is initialised in $$O(n_1)$$ time.\n2. Precompute `right_matches`:\n    - Iterates over `word1` from right to left, comparing with a single character of `word2` in each iteration, thus taking $$O(n_1)$$.\n3. Build sequence of indices:\n    - Another linear pass over `word1` to form the sequence takes $$O(n_1)$$.\n\n### Space Complexity: $O(\uD835\uDC5B)$\n1. `right_matches`:\n    - This array uses $$O(n_1)$$ space to store $$n_1$$ integers.\n2. `output`:\n    - The output sequence is an array that uses up to $$O(n_2)$$ space.\n\n# Best, Worst, and Average Case Analysis\n### Time Complexity\nIn all cases, $2\\times O(n_1)$ is needed to initialise and to precompute `right_matches`.\n1. Best-case: $O(2n_1+n_2)$ = $O(n)$\n    - When building the output sequence, every character is a match, requiring only to traverse $n_2$ indices (the length of `word2`) before the early exit.\n2. Worst-case: $O(3n_1)$ = $O(n)$\n    - The entire `word1` is traversed during sequence building to find that there is no valid sequence of indices.\n3. Average-case: $O(2n_1+n_2<x<3n_1)$ = $O(n)$\n    - On average, more than $n_2$ indices have to be traversed during sequence building due to multiple mismatches, but the sequence may be completed before traversing the entire $n_1$ indices of `word1`.\n\n### Space Complexity\nIn all cases, $O(n_1)$ is needed to store `right_matches` array.\n1. Best-case: $O(n_1)$ = $O(n)$\n    - When there are no matches between `word1` and `word2` and the output sequence is empty.\n2. Worst-case: $O(n_1+n_2)$ = $O(n)$\n    - A valid sequence is found, meaning output sequence is completely filled up to the length of `word2`, taking $O(n_2)$ space.\n3. Average-case: $O(n_1+n_2)$ = $O(n)$\n    - On average, either a valid sequence is found, or the output sequence is filled up partially, before the entire `word1` is traversed fully to reveal no valid sequence. So the output sequence may take less than $O(n_2)$ space.\n### Summary\n| Scenario | Time Complexity | Space Complexity |\n| - | - | - |\n| Best Case | $O(n)$ | $O(n)$ |\t\n| Worst Case | $O(n)$ | $O(n)$ |\n| Average Case | $O(n)$ | $O(n)$ |\n***\nCheck out my solutions to other problems here! \uD83D\uDE03\n*https://leetcode.com/discuss/general-discussion/5942132/my-collection-of-solutions*\n***
['Two Pointers', 'Greedy', 'Prefix Sum', 'Python3']