Sliding window | Multiple approaches | commented
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```python3 []\nclass Solution:\n    def minimumScore(self, s: str, t: str) -> int:\n        # Naive approach would be n * (1 << n), try all possibilities.\n        # Option wise - two options remove / don\'t, for don\'t we need to find the very next index of the t[i] term we\'re looking at in s which can be done in constant time with list of dictionary or something. state (idx, lastTakenIdx) -> O(n ^ 2)\n        # Non - dp O(n ^ 3) solution, we don\'t care about what all we remove we only care about left and right, we can try all possible left and rights in O(n ^ 2) and checking subsequence is O(n). We can optimize this with binary search over answer [left..right] -> [left..left+k], O(n ^ 2 * log2n)\n        # We can use preprocessing to optimize this further, greedily how short of a prefix we need to make sure t[:left] is a subsequence we can calculate this in linear time, same logic for t[right:] how short of a suffix we need to make t[right:] a subsequence if there is no overlap in this prefix and suffix then we have a valid [left..right], now this can be solved with sliding window because for any [left..right] if there is an overlap in prefix and suffix the only option is to increase right to increase the window (we don\'t decrease left), and if there is no overlap we can try to increase the left to decrease the window.\n        n = len(s)\n        m = len(t)\n        # What min idx in s we need to make t[:i + 1] a subsequence of s\n        prefix = [n] * m\n        # What max idx in s we need to make t[i:] a subsequence of s\n        suffix = [-1] * m\n        \n        # calculating prefix\n        i, j = 0, 0\n        while i < n and j < m:\n            if s[i] == t[j]:\n                prefix[j] = i\n                i += 1\n                j += 1\n            else:\n                i += 1\n        \n        # calculating suffix\n        i, j = n - 1, m - 1\n        while i > -1 and j > -1:\n            if s[i] == t[j]:\n                suffix[j] = i\n                i -= 1\n                j -= 1\n            else:\n                i -= 1\n        \n        def getPrefix(idx: int) -> int:\n            if idx < 0: return -1\n            else: return prefix[idx]\n        \n        def getSuffix(idx: int) -> int:\n            if idx >= m: return n\n            else: return suffix[idx]\n        \n        ans = m\n        r = 0 # excluding r [l, r), why? because 0 is also possible.\n        for l in range(m):\n            while r <= m and getPrefix(l - 1) >= getSuffix(r):\n                r += 1\n            if r <= m and getPrefix(l - 1) < getSuffix(r):\n                ans = min(ans, (r - l))\n                if ans == 0: return 0\n        return ans\n```
['Python3']