Python | Sliding Window | Linear Time | Easy to Understand
Intuition\n Describe your first thoughts on how to solve this problem. \nWe can remove whole range from left to right\n\n# Approach\n Describe your approach to 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nWe can remove whole range from left to right\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nTry removing each range and check if remaining string form valid subsequence or not. To do this we need to precompute match indices in string s. Then using sliding window we can find minimum window size satisfying above condition.\n\n# Complexity\n- Time complexity: $$O(n)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(n)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```python []\nclass Solution:\n    def minimumScore(self, s: str, t: str) -> int:\n        prefix, suffix = [len(s)] * (len(t) + 1), [-1] * (len(t) + 1)\n        prefix[0], suffix[-1], tIdx = -1, len(s), 0\n        for idx in range(len(s)):\n            if tIdx >= len(t): break\n            if s[idx] == t[tIdx]: \n                prefix[tIdx + 1] = idx\n                tIdx +=1\n        tIdx = len(t) - 1\n        for idx in reversed(range(len(s))):\n            if tIdx < 0: break\n            if s[idx] == t[tIdx]: \n                suffix[tIdx] = idx\n                tIdx -=1\n        if prefix[-1] < len(s): return 0\n        left, res = 0, max(len(s), len(t))\n        for right in range(len(t)):\n            left +=1\n            while left <= right and prefix[left] < suffix[right + 1]: \n                left +=1\n            left -=1\n            if prefix[left] < suffix[right + 1]: \n                res = min(res, right - left + 1)\n        return res\n```
['Sliding Window', 'Suffix Array', 'Prefix Sum', 'Python', 'Python3']