[Python] left and right O(n) with detailed explanation and example
Intuition\n Describe your first thoughts on how to solve this problem. \nThis is adpated from https://leetcode.com/votrubac/\'s solution.\n\nThe first observati
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThis is adpated from https://leetcode.com/votrubac/\'s solution.\n\nThe first observation is that since the number of removals doesn\'t matter, we just need to figure out the start index on the left and the end index on the right. In other words, we want to find l and r such that t[:l] + t[r:] is a substring of s.\n\nIn the first pass, we find for each position in s **the largest index r of t** that would have to be removed for t be a substring s upto that index. i.e. **t[suffix[i]+1:] is a substring of s[i:] and suffix[i] is the least index such that this holds**.\n\nIn the second pass, we find **the largest index l of t** that is a substring of s[:i]. **The difference, (suffix[i] - l+1) would be the length that need to be removed to make t a substring of s.**\n\n**This way, we find the least score for such that t[:r] is a substring s[:i] and t[l+1:] is a substring of s[i:]. By taking the minimum over these scores, we find the true minimum score.**\n\n# Example\n\ns =[a,b,a,c,a,b,a], len(s) = 7\nt = [b,z,a,a], len(t) = 4\ninitialize suffix with -1:\nsuffix = [-1,-1,-1,-1,-1,-1,-1], len(suffix) = 7\n\n---\n**Go from left to right for both s and t in the first pass.**\ns = [a,b,a,c,a,b,**a**], len(s) = 7, i = 6\nt = [b,z,a,**a**], len(t) = 4, r = 3\nfirst, set suffix[i] = r\nsuffix = [-1,-1,-1,-1,-1,-1, **3**]\nsince s[i] == t[r], we can decrease r by 1, to account for the fact that t[3:] is a substring of s[6:], which will be used in the second pass\n\n---\ns = [a,b,a,c,a,**b**,a], len(s) = 7, i = 5\nt = [b,z,**a**,a], len(t) = 4, r = 2\nsince s[i] != t[r], the last index (counting from left to right) of t that is not a substring of s[5+1:] is 2, so we have\nsuffix = [-1,-1,-1,-1,-1, **2**, 3]\n\n---\ns = [a,b,a,c,**a**,b,a], len(s) = 7, i = 4\nt = [b,z,**a**,a], len(t) = 4, r = 2\nsimilar to the first case, we get \nsuffix = [-1,-1,-1,-1,**2**, 2, 3] and move r to 1\n\n---\ns = [a,b,a,c,a,b,a], len(s) = 7, i = 3\nt = [b,**z**,a,a], len(t) = 4, r = 1\nNote that now r points to z, which is not part of s. So, the pointer r will not decrease from now on. In the end,\nsuffix = [1,1,1,1,2,2,3]\n\n---\n\n**Start from left to right for the second pass.**\nans = r + 1 = 2 because we can remove everything including z and the rest of t (aa) would be a substring of s.\n\ns = [**a**,b,a,c,a,b,a], len(s) = 7, i = 0\nt = [**b**,z,a,a], len(t) = 4, r = 0\nsuffix = [1,1,1,1,2,2,3]\nsince s[i]!=t[r], the substring we can form here is t[:r] + t[suffix[i]+1:] = ""+"aa" = "aa", and ans = min(2, 2-0) = 2.\n\n---\ns = [a,**b**,a,c,a,b,a], len(s) = 7, i = 1\nt = [**b**,z,a,a], len(t) = 4, r = 0\nsuffix = [1,1,1,1,2,2,3]\nsince s[i]==t[r], the substring we can form here is t[:r+1] + t[suffix[i]+1:] = "b"+"aa" = "baa", we update r to 1, ans = min(2, 1+1-1) = 1.\n\n\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(n), since we pass through the array twice.\n\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(n) for the suffix array\n\n# Code\n```\nclass Solution:\n    def minimumScore(self, s: str, t: str) -> int:\n        suffix = [-1]*len(s) #last index of t that is not accounted for at i in s\n        r = len(t)-1\n        for i in reversed(range(len(s))): \n            suffix[i] = r \n            if 0 <= r and s[i] == t[r]: \n                r -= 1\n        # we know things after r are already a substring of s, so at most need to remove r+1 things\n        ans = r + 1 \n        l = 0 \n        for i, ch in enumerate(s): \n            # at i, on the right, we need to remove to suffix[i], on the right, we need to remove from l\n            if l < len(t) and s[i] == t[l]: \n                # t[l] matched with s[i], so for i+1, we don\'t have to remove s[l]\n                l += 1\n            ans = min(ans, max(0, suffix[i] - l + 1))\n        return min(ans, len(t)-l)\n\n```
['Python3']