Python Medium
python3 []\nclass Solution:\n    def validSequence(self, A: str, B: str) -> List[int]:\n        \'\'\'\n        small idea: brute force each letter?\n        \n
```python3 []\nclass Solution:\n    def validSequence(self, A: str, B: str) -> List[int]:\n        \'\'\'\n        small idea: brute force each letter?\n        \n        correlary: start from the back of pattern, the first letter that we cant find in s we do an O(26) dp on it\n        \n        \n        q1: is there a subseq of word2 in word1\n        -> greedy O(N)\n        \n        q2: return indicides of the lex smallest subseq of word2 in word1\n        -> greedy O(N)\n        \n        q3:\n        if there a subseq of word2 in word1, with exactly one free letter?\n        O(N) * 2\n        \n        q4: return indicides of the lex smallest subseq of word2 in word1, with exactly one free letter\n        \n        \n        q3 and q4 have notes of dp (skip, dont skip)\n        \n        \n        starting from the back to d\n        \n        vabc\n        \n        dabc\n        \n        \n        M * N dp is obvious\n        \n        how do we do exactly 1 different?\n        \n        we have O(N) exact same\n        \n        \n        \n        maybe this one is prefix suffix\n        \n        meaning we cna brute force prefix suffix\n        \n        we can randomly match any 2 indices i and j\n        \n        after that, we can brute force\n        \n        \n    \n         \n        if you pick one index, problem is an easy O(n) each side\n        \n        however, if you pick n indices, then its n^2\n        \n        so, we want to preprocess pref suff in O(nlogn) time or better\n        \n        for i in range(N):\n            if good(pref[:i] + suff[i + 1:]):\n                return pref_indices + i + suff_indices\n        \n        \n        \n        good_pref(piece1 0 to ending at index-1) + free(index) + good_suff(piece2 starting at index+1 to N-1)\n        \n        \n        iterating through indices is O(n)\n        \n        if good can run in logn, then we can do it\n        \n        \n        good_pref(i, length)\n        \n        does the subsequence of the first length letters of B exist in the first i letters of A?\n        \n        \n        good_suf(i, length)\n        \n        does the subsequence of the last length letters of B exist in the last i letters of A?\n            \n        \n        We can preprocess this!\n        \n        \n        \n        \n        \n        \'\'\'\n        M, N = len(A), len(B)\n        \n        best_pref = [0] * M\n        \n        \n        i, j = 0, 0\n\n        while i < M:\n            if j == N:\n                best_pref[i] = j\n                i += 1\n                continue\n            \n            elif A[i] == B[j]:\n                best_pref[i] = j + 1\n                i += 1\n                j += 1\n                \n            else:\n                best_pref[i] = j\n                i += 1\n                \n                \n        A_rev = A[::-1]\n        B_rev = B[::-1]\n        \n        best_suf = [0] * M\n        \n        \n        i, j = 0, 0\n\n        while i < M:\n            if j == N:\n                best_suf[i] = j\n                i += 1\n                continue\n            \n            elif A_rev[i] == B_rev[j]:\n                best_suf[i] = j + 1\n                i += 1\n                j += 1\n                \n            else:\n                best_suf[i] = j\n                i += 1\n                \n                \n                \n        best_suf.reverse()\n        \n#         print(A)\n#         print(B)\n#         print(best_pref)\n#         print(best_suf)\n#         print()\n        \n        \n        def get_indices(i, j, total):\n            if total == 0:\n                return []\n            arr = []\n            while total and i < M and j < N:\n                if A[i] == B[j]:\n                    arr.append(i)\n                    i += 1\n                    j += 1\n                    total -= 1\n                else:\n                    i += 1\n                    \n                \n                \n            return arr\n                \n        \n        index = 0\n        while index < N and A[index] == B[index]:\n            index += 1\n            \n        if index == N:\n            return [i for i in range(N)]\n        \n        \n        while index < M:\n            # print(A, B, index, best_pref, best_suf)\n            if index == 0:\n                if best_suf[index + 1] >= N - 1:\n                    # return [0]\n                    return [0] + get_indices(1, 1, N - 1)\n            \n            elif index == M - 1:\n                # print("hi", A, B)\n                if best_pref[M - 2] >= N - 1:\n                    # return [0]\n                    return get_indices(0, 0, N - 1) + [M - 1]\n            \n                \n            else:\n                # print(A, B, index, best_pref[index - 1], best_suf[index + 1])\n                if best_suf[index + 1] + best_pref[index - 1] >= N - 1:\n                    return get_indices(0, 0, best_pref[index - 1]) + [index] + get_indices(index + 1, 1 + best_pref[index - 1], N - 1 - best_pref[index - 1])\n                \n        \n            index += 1\n        \n\n        return []\n        \n        \n        \n        \n        \n        \n        \n```
['Python3']