🔥Python3🔥 Greedy with comments
Observation: Everything in between left and right can be removed.\n\npython\nclass Solution:\n    def minimumScore(self, s: str, t: str) -> int:\n        # Take
**Observation**: Everything in between ```left``` and ```right``` can be removed.\n\n```python\nclass Solution:\n    def minimumScore(self, s: str, t: str) -> int:\n        # Take care of the case where t is already a substring of s, return 0 in this case.\n        j = 0\n        for i in range(len(s)):\n            if s[i]==t[j]: j+=1\n            if j==len(t): return 0\n        \n        # Moving forward, store the first letter\'s index in t that needs to be removed if s ends at i.\n        firstRemovedIndexFromLeft = [0]*len(s)\n        left = 0\n        for i in range(len(s)):\n            if s[i]==t[left]:\n                left += 1\n            firstRemovedIndexFromLeft[i] = left\n\n        # Worest case, we remove the first and last letter in t.\n        res = len(t)\n        \n        # Moving backward, at each position i in s, there are two cases:\n        # (1) the firstRemovedIndexFromLeft[i] <= first removed index from right,\n        #       This is a valid case in the sense that we can \n        #       basically, remove everything in between these two indices, including these two indices.\n        #       i.e.,\n        #       s = \'aabbbaa\'\n        #       t = \'aazzzaa\'\n        #       firstRemovedIndexFromLeft  = [1, 2, 2, 2, 2, 2, 2]\n        #       firstRemovedIndexFromRight = [4, 4, 4, 4 ,4, 5, 6] (We don\'t actually put the right in arr like this, but just for easy understanding here)\n        #       when i=3, firstRemovedIndexFromLeft[i] = 2 and right = 4, \n        #       so we try to update res, if the score (right-left+1) is smaller.\n        #\n        # (2) left > right, this is an invalid case to consider both indices.\n        #       In this case, we basically just remove everything from 0 to index right, \n        #       score is (right - 0 + 1), where 0 is the left index. Update res if score is smaller.\n        right = len(t) -1 \n        for i in reversed(range(len(s))):\n            if right>=firstRemovedIndexFromLeft[i]:\n                res = min(right-firstRemovedIndexFromLeft[i]+1,res)\n            if s[i] == t[right]:\n                right -= 1\n            res = min(res, right+1)\n            \n        return res\n```\nIs this called greedy approach or dp? Or it has an other name? Plesse leave a comment if you know the answer, thanks.\n\n**Upvote** if you like this post.\n\n**Connect with me on [LinkedIn](https://www.linkedin.com/in/meida-chen-938a265b/)** if you\'d like to discuss other related topics\n\n\uD83C\uDF1F If you are interested in **Machine Learning** || **Deep Learning** || **Computer Vision** || **Computer Graphics** related projects and topics, check out my **[YouTube Channel](https://www.youtube.com/@meidachen8489)**! Subscribe for regular updates and be part of our growing community.
[]