Commented & Explained C++ | Understandable | O(n)
Intuition\nTo form intuition for this problem, we need to understand the problem description thoroughly. The goal is to find the minimum score of t such that t 
# Intuition\nTo form intuition for this problem, we need to understand the problem description thoroughly. The goal is to find the minimum score of t such that t is a subsequence of s. The score is defined as the difference between the maximum and minimum indices of all removed characters in t.\n\nWith this in mind, we can think of the problem as finding the longest prefix and suffix of t that are substrings of s. We start by finding the suffix by iterating through s in reverse order and keeping track of the indices of characters in s that match characters in t. This creates a dp array that stores the indices in s of the corresponding characters in t.\n\n# Explanation\nThe minimumScore function takes in two strings s and t and returns the minimum possible score to make t a subsequence of s. The score is calculated as described in the problem statement:\n\n* if no characters are removed from the string t, then the score is 0\n* otherwise, the score is equal to the difference between the maximum index and the minimum index among all removed characters, plus 1\n\nThe function starts by initializing the variable ss to the length of s, st to the length of t, and k to st - 1. The dp array is initialized with st elements all equal to -1.\n\nThe next step is to build the suffix of t. This is done by iterating through s from the end to the beginning and checking if the current character of s is equal to the current character of t starting from the end. If they are equal, then the index of the character in s is recorded in the dp array. The k variable is decremented each time a match is found.\n\nAfter building the suffix, the function moves on to building the prefix of t by iterating through s from left to right. The j variable keeps track of the position of the current character of t that is being matched. The k variable is updated to the smallest index of dp that is greater than the current index i of s. The result res is then set to the minimum between res and the difference between k and j + 1.\n\nFinally, the function returns the res variable, which represents the minimum possible score to make t a subsequence of s.\n\nUPVOTE if you find helpful!\n\n# Complexity\nTC: O(n)\n\n# Code\n```\nclass Solution {\npublic:\n    int minimumScore(string s, string t) {\n        // initialize the length of strings `s` and `t`\n        int ss = s.size(), st = t.size();\n\n        // `k` keeps track of the last matched character in t from the right\n        int k = st - 1;\n\n        // initialize the dp array with all elements as -1\n        vector<int> dp(st, -1);\n\n        // iterate from the end of `s` and match characters from the end of `t`\n        for (int i = ss - 1; i >= 0 && k >= 0; --i) {\n            // if the character at `i` in `s` matches the character at `k` in `t`, \n            // update the `dp` array with the index `i`\n            if (s[i] == t[k]) {\n                dp[k--] = i;\n            }\n        }\n\n        // `res` stores the minimum score, initially set to `k + 1`\n        int res = k + 1;\n\n        // iterate over `s` and `t` from the start\n        for (int i = 0, j = 0; i < ss && j < st && res > 0; ++i) {\n            // if the character at `i` in `s` matches the character at `j` in `t`, \n            // increment `j`\n            if (s[i] == t[j]) {\n                // for each matched character, update `k` to the next character in `t` \n                // that is yet to be matched\n                for (; k < t.size() && dp[k] <= i; ++k);\n                // update `res` with the minimum value of `res` and `k - (j + 1)`\n                res = min(res, k - (++j));\n            }\n        }\n\n        // return the minimum score\n        return res;\n    }\n\n};\n```\n\nThanks to @votrubac for code.\n\nUPVOTE if you find helpful!\n
['C++']