O(n) time and space solution using a queue and a stack
Intuition\n\nMy initial thought was that this should be a dynamic programming problem as it superficially sounds related to the classic longest subsequence prob
# Intuition\n\nMy initial thought was that this should be a dynamic programming problem as it superficially sounds related to the classic longest subsequence problem (e.g., see Cormen\'s Algorithms Text, DP Chapter). However, upon closer inspection, the problem is asking for something much simpler: the minimum distance between the first index that must be removed and the last index that must be removed to make the second string a subsequence of the first.\n\nNote that this is actually not equivalent to the LCS problem. As an example:\n\nLeft: complain\nRight: paning\n\nThe lonest common subsequence is "pain"; however, the subsequence that solves the problem is actually "pan" ("ing" get removed, which gives a minimum score of 3).\n\nThe correct way to think about it is to really focus on delaying the first character that should be removed while similtaneously considering its impact on the last character that should be removed.\n\nThe best way to explain the intuition behind my algorithm is with an example. Consider again:\n\nLeft: complain\nRight: paningoman\n\nThe minimum score is the minimum value of (maxRemove - minRemove). To maximimize minRemove (which reduces the score), we need to maximize the length of the prefix of "paning" that occurs in "complain". Note that \'p\' occurs at index 3 in complain, \'a\' occurs at index 5 (must be at an index greater than 3 to preserve subsequence order), \'n\' occurs at index 7, and then \'i\' can not longer exist in the subsequence of "comPlAiN" (where capitical letters should how the prefix "pan" becomes a subsequence of "complain"). Note that if we select "pan" as our subsequence, it means that we must remove all character of the suffix "ingoman", which gives us a score of 7.\n\nWe could also work backwards to minimize maxRemove by considering how much of the suffix of "paningoman" we can turn into a subsequence of "complain". Note that the last \'n\' occurs at index 7 in "complain", \'a\' occurs at index 5, \'m\' occurs at index 2, and \'o\' occurs at index 1. If we select "oman" as our subsequence, then we would need to remove the prefix "paning", which results in a score of 6 (which is better than 7).\n\nWe can also consider a hybrid of what is described in the last two paragraphs. We can simultaneosly select a prefix and a suffix of "paningoman" that attempts to increase minRemove and decrease maxRemove in a way that minimizes the overall score.\n\nNote that the prefixes of "paningoman" that fit as a subsequence in "complain" occur at indices:\n\n3, 5, 7 (this will be a queue as we will read element FIFO)\n\nNow traversing backwards through the two input strings, we note that the suffixes of "paningoman" that fit as a subsequence in "complain" occur at indices:\n\n1, 2, 5, 7 (this will be a stack as we will read elements LIFO)\n\nWe will refer to the first queue as `leftCand` or candidates that we will incrementally add to a prefix of "paningoman" that will exist in our optimal subsequence. We will refer to the second stack as `rightUsed`, which reflects the suffix of "paningoman" that will exist in our optimal subsequence. We will incrementally remove elements from `rightUsed` as we add elements of `leftCand`.\n\nThe first subsequence we will consider will be the characters at indices\n\n1, 2, 5, 7\n\nwhich is exactly equal to `rightUsed`. This corresponds to "oman". The score is 6 since we must remove "paning".\n\nNext, we want to add the first 3 from `leftCand` into our subsequence. But to do this, we must remove the 1 and 2 (since they occur before 3 and we need to maintain the subsequence property). This gives us\n\n3, 5, 7\n\nThis corresponds to "pan", which removes the substring "aningom", which gives us a score of 7 (not minimal, so 6 is still the best).\n\nNext, we want to add the second 5 from `leftCand` into our subsequence. But to do this, we have to remove the existing 5, again, since we want to preserve the subsequence property. This gives us\n\n3, 5, 7\n\nwhich is identical to the previous case. It turns out we will also get 3, 5, 7 when we insert the last 7 from `leftCand` and remove the 7 from `rightUsed`.\n\nThe final answer is that the minimum score is 6.\n\n\n# Approach\n\n1. Generate a queue `leftCand` consisting of the indices in `leftString` corresponding to the first n consecutive characters (i.e., prefix) of `rightString`. Note that this queue can be empty if the first character of `rightString` does not exist.\n2. Generate a stack `rightUsed` consisting of the indices in `leftString` corresponding to the last n consecutive character (i.e., suffix) of `rightString`. Note that elements being removed from this stack should be ascending order. Also, note that this stack can be empty if the last chacter of `leftString` does not exist in `rightString`.\n3. First calculate the score based on the subsequence implied by `rightUsed`. If there are no elements in `leftCand`, this this will be the minimum score.\n4. While `leftCand` is non-empty, pop the next element from the queue. Remove any indices from `rightUsed` that are less than or equal to the element popped off of `leftCand`. The list of all elements popped off of `leftCand` so far and the remaining (non-popped) elements of `rightUsed` for the next candidate subsequence. Calculate its score and check if it is minimal.\n5. Return the minimum score found.\n\n\n# Complexity\nAssume that the left string has length n and the right string has length m.\n\n**Time complexity:** \nCreating the `leftCand` queue and `rightString` stack both require a single full pass of the left string, which requires O(n) steps.\n\nThe main loop requires `|leftCand| + |rightUsed|` steps which is maximally O(2 x min(n, m)) = O(n).\n\nThe overall time complexity is O(n).\n\n**Space complexity:**\nThe only addition space created are from the queue `leftCand` and the stack `rightUsed`. This will be O(1) in the best case and O(n) in the worst case.\n\n# Code\nThe following python3 code passed all test cases. It uses the `deque` class to create the necessary queue and stack.\n\n```\nfrom collections import deque\n\nclass Solution:\n    \n    def getLeftIndices(leftString, rightString):\n        rightIdx = 0\n        leftCand = deque()\n        for idx, letter in enumerate(leftString):\n            if letter == rightString[rightIdx]:\n                leftCand.append(idx)\n                rightIdx += 1\n                if rightIdx >= len(rightString):\n                    break\n        return leftCand\n\n    def getRightIndices(leftString, rightString):\n        rightIdx = len(rightString) - 1\n        rightCand = deque()\n        for idx, letter in enumerate(leftString[::-1]):\n            if letter == rightString[rightIdx]:\n                rightCand.appendleft(len(leftString) - 1 - idx)\n                rightIdx -= 1\n                if rightIdx < 0:\n                    break\n        return rightCand\n\n    def minimumScore(self, s: str, t: str) -> int:\n        leftCand = Solution.getLeftIndices(s, t)\n        rightUsed = Solution.getRightIndices(s, t)\n\n        minRemove = 0\n        maxRemove = len(t) - 1 - len(rightUsed)\n        minScore = maxRemove - minRemove + 1\n\n        score = minScore\n        while minScore > 0 and len(leftCand) > 0: \n            if len(rightUsed) == 0 or leftCand[0] < rightUsed[0]:\n                minRemove += 1\n                leftCand.popleft()\n            else:\n                maxRemove += 1\n                rightUsed.popleft()\n            score = maxRemove - minRemove + 1\n            minScore = min(score, minScore)\n\n        return minScore\n\n```
['Python3']