2565. Subsequence With the Minimum Score
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 []\nfrom math import ceil\n\nclass Solution:\n    def minimumScore(self, s: str, t: str) -> int:\n        # We find the suffixes of t that are a subsequence\n        # of s. We can do this by using two pointers. We start\n        # at the end of s and t. We loop through s. If\n        # the current character in t matches s, that means\n        # that character is part of a subsequence of s.\n        # We store the index of the character in s it matches\n        # for later.\n        left_of_suffix_index = len(t)-1\n        suffix_indices = []\n        for s_index in range(len(s)-1, -1, -1):\n            # The score is zero if we don\'t need to remove any characters\n            # from t.\n            if left_of_suffix_index < 0:\n                return 0\n            elif s[s_index] == t[left_of_suffix_index]:\n                left_of_suffix_index -= 1\n                suffix_indices.append(s_index)\n        # Let\'s say that we delete all of the characters before the suffix.\n        # The score would be:\n        # left_of_suffix_index - 0 + 1 = left_of_suffix_index + 1\n        # We\'ll start with that value\n        result = left_of_suffix_index + 1\n        # Now we want to consider forming a subsequence of s by\n        # using a prefix or using a mix of a prefix and suffix.\n        # The intuition behind this is that characters in the middle\n        # do not matter: only the boundaries do!\n        # So we loop through each potential prefix and see what\'s\n        # the largest suffix we can add to it without adding the same\n        # character in s twice.\n        right_of_prefix_index = 0\n        for s_index in range(len(s)):\n            # The score is zero if we don\'t need to remove any characters\n            # from t.\n            if right_of_prefix_index >= len(t):\n                return 0\n            elif s[s_index] == t[right_of_prefix_index]:\n                # Let\'s figure out the largest suffix\n                # we can combine with this prefix. That\n                # is the subsequence that uses the most\n                # characters in s that have an index\n                # greater than s_index. We can use\n                # binary search since suffix_indices is\n                # in decreasing order.\n                if suffix_indices:\n                    left = 0\n                    right = len(suffix_indices) - 1\n                    while left < right:\n                        midpoint = ceil((left + right) / 2)\n                        if suffix_indices[midpoint] > s_index:\n                            left = midpoint\n                        else:\n                            right = midpoint - 1\n                    if suffix_indices[right] > s_index:\n                        # On the right, we remove character at index\n                        right_removal_index = len(t) - 1 - (right + 1)\n                        # On the left, we remove a character at index\n                        left_removal_index = right_of_prefix_index + 1\n                        # So the score is\n                        score = right_removal_index - left_removal_index + 1\n                        result = min(result, score)\n                right_of_prefix_index += 1\n        # Now we consider using only a prefix.\n        result = min(result, len(t) - 1 - right_of_prefix_index + 1)\n        return result\n        \n```
['Python3']