Python clean O(n), match prefix and suffix
Code\npy\nclass Solution:\n    def minimumScore(self, s: str, t: str) -> int:\n        def scan(s, t):\n            ans = [0]\n            i = 0\n            fo
# Code\n```py\nclass Solution:\n    def minimumScore(self, s: str, t: str) -> int:\n        def scan(s, t):\n            ans = [0]\n            i = 0\n            for c in s:\n                if i < len(t) and t[i] == c:\n                    i += 1\n                ans.append(i)\n            return ans\n        r1 = scan(s, t)\n        r2 = reversed(scan(s[::-1], t[::-1]))\n        best = max(map(sum, zip(r1, r2)))\n        return max(0, len(t) - best)\n```\n\n# Intuition\nMatch a prefix of `t` to a prefix of `s` and match a suffix of `t` to a suffix of `s`. We want to maximize the sum of the lengths of the prefix and suffix of `t`.\n\n# Approach\n`scan(s, t)` finds, for each prefix of `s`, the longest prefix of `t` such that the prefix of `t` is a subsequence of the prefix of `s`. We scan once forwards to get `r1` and once backwards to get `r2`.\nNow, for any index `j` we can split `s` to a prefix and a suffix. `t[:r1[j]]` is the longest prefix that matches the prefix `s[:j]` and `t[r2[j]:]` is the longest suffix that matches the suffix `s[j:]`. Then, `r1[j] + r2[j]` is the total length of prefix and suffix so `len(t) - r1[j] + r2[j]` is the best score if we split `s` at `j`.\n\n# Example\n\n```\ns: "abacaba"\nt: "bzaa"\nr1: [0, 0, 1, 1, 1, 1, 1, 1]\nr2: [2, 2, 2, 2, 2, 1, 1, 0]\nlen(t) - r1[j] + r2[j] for each j:\n    [2, 2, 1, 1, 1, 2, 2, 3]\nanswer: 1\n```\n\n# Complexity\n- Time complexity:\n$$O(n + m)$$ where $$n, m$$ are the lengths of `s` and `t` respectively\n\n- Space complexity:\n$$O(n)$$ where $$n$$ is the length of `s`
['Python3']