Left and Right O(n) -- Python version
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\nLeft pass once for each index i in t, find the smallest index j in s such
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\nLeft pass once for each index i in t, find the smallest index j in s such that t[: i+1] is a subsequence of s[: j+1]. Store the answer in an array (leftArr).\nIf such j does not exist for some i, then by default leftArr[i] = -1.\n\nSimilarly, right pass once for each i in t, find the largest index j in s such that t[i: ] is a subsequence of s[j: ]. Store the answer in an array (rightArr).\nIf such j does not exist for some i, then by default rightArr[i] = -1.\n\nFinally, pass t from right to left, for each index $right$ satisfying $rightArr[right]!=-1$, look for the largest index $left$ of t, such that $leftArr[left]!=-1$ and $leftArr[left] < rightArr[right]$.\nAbove can guarantee that t[ :left] + t[right: ] is a subsequence of s. \nWe simply need to find the $(left, right)$ pair which minimizes (right-1-left).\n\n# Complexity\n- Time complexity:\n$$O(n)$$\n\n- Space complexity:\n$$O(n)$$\n\n# Code\n```\nclass Solution:\n    def minimumScore(self, s: str, t: str) -> int:\n        m = len(s)\n        n = len(t)\n        rightArr = [-1 for _ in range(n)]\n        leftArr = [-1 for _ in range(n)]\n\n        j = 0 \n        for i in range(n):\n            if j >= m:\n                break\n            while j < m and s[j] != t[i]:\n                j+=1\n            if j < m:\n                leftArr[i] = j\n                j += 1\n        \n        j = m-1\n        for i in reversed(range(n)):\n            if j < 0:\n                break\n            while j >= 0 and s[j] != t[i]:\n                j -= 1\n            if j >= 0:\n                rightArr[i] = j\n                j -= 1\n\n        right = n\n        left = -1\n        for i in range(n):\n            if leftArr[i] == -1:\n                break\n            left = i\n        res = right-1-left\n        right = n-1\n        while right >= 0 and (rightArr[right]!= -1):\n            boundary = rightArr[right]\n            left = min(left, right-1)\n            while left>=0 and leftArr[left] >= boundary:\n                left -= 1\n            res = min(res, right-1-left)\n            right -= 1\n        return res\n\n            \n\n```
['Python3']