Forward and Backward passes in Python, Faster than 85%
Approach\n Describe your approach to solving the problem. \nThis solution tries to find the best pivot for merging a prefix and a suffix so that the score is mi
# Approach\n<!-- Describe your approach to solving the problem. -->\nThis solution tries to find the best pivot for merging a prefix and a suffix so that the score is minimized. To do so, the forward scores are precomputed for prefixes, and the backward scores are also computed for suffixes. Finally, the answer is `min(forward[i]+backward[i+1]) for all i`. \n\nYou can also precompute one of forward or backward scores only, and compute the scores of the other direction in place. However, I find it is faster to precompute both directions of scores and find the answer with `min()`. \n\n# Complexity\n- Time complexity: $$O(N)$$, where $$N$$ is the length of `s`. \n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: At least one of the forward and the backward scores should be precomputed and stored. The space complexity is $$O(N)$$.\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution:\n    def minimumScore(self, s: str, t: str) -> int:\n        j = 0\n        forward = [0]\n        for c in s:\n            if t[j] == c:\n                j += 1\n            if j >= len(t):\n                return 0\n            forward.append(j)\n            \n        j = len(t) - 1\n        backward = [j]\n        for c in reversed(s):\n            if t[j] == c:\n                j -= 1\n            backward.append(j)\n        return min(b - a for a, b in zip(forward, reversed(backward))) + 1              \n```
['Python3']