C++ Clean, Explained.
Solution \n\nIf we remove some substring of $t$, we are left with a prefix (possibly empty), and a suffix (possibly empty), of $t$. This prompts us to precalcul
# Solution \n\nIf we remove some substring of $t$, we are left with a prefix (possibly empty), and a suffix (possibly empty), of $t$. This prompts us to precalculate for each prefix/suffix, what is the minimum prefix/suffix of $s$ that we need for the prefix/suffix of $t$ to be a subsequence of. \n\nFirstly, finding the longest prefix of a string $t$ that is a subsequence of $s$ can be done in $O(|s|+|t|)$. This is done by using two pointers, one for each string. \n\nLet $i$ be the pointer for $s$, and $j$ be the pointer for $t$. \n\nNote that as we are incrementing  $j$, the pointer $i$ is the rightmost position in the \n\n\nin $s$ of the prefix of $t$ up to $j$. Thus, we are able to find, for each prefix of $t$, what is the minimal size of the prefix of $s$ (the maximum index) such that $t$ is a subsequence of that prefix. In my implementation, I use an array $left$, and store $i$ in $left_j$. Conversely, this logic can also be applied to find the minimal suffix of $s$ such that it contains a subsequence of a suffix of $t$. I store the minimum index $i$ in $right_j$ (the smallest suffix of s such that the suffix from $t$ is a subsequence of it). \n\nNow that we have $left$ and $right$, we can fix the prefix (we will call $a$ the last index of the prefix) of $t$ that we will keep, and binary search for the leftmost suffix of $t$ such that there is no overlap in $s$. (We want a prefix and a maximal suffix to minimize r-l+1, but we do not want them to overlap in letters in $s$, or else we will not have a subsequence). Thus, we can binary search for the biggest suffix (we will call $b$ the first index of the suffix) of $t$ that satisfies the following conditions: \n\n$a$ < $b$\n$left_a$ $<$ $right_b$\n\nSee my implentation below for details. \n\nThe time complexity is $O(NlogN)$, \n\n```cpp\nclass Solution {\npublic:\n    int minimumScore(string s, string t) {\n        int n = s.size(), m = t.size(); \n        vector<int> l(m, -1), r(m, -1); //left, right arrays. \n        int j = 0; \n        for (int i = 0; i < n; ++i) {\n            if (j >= m) break; \n            if (s[i] == t[j]) {\n                l[j] = i; //for a prefix of t from 0...j, i is the greatest \n                //index in s such that it is a subsequence\n                j++; \n            }\n        }\n        j = m-1; \n        for (int i = n-1; i >= 0; --i) {\n            if (j < 0) break; \n            if (s[i] == t[j]) {\n                r[j] = i; \n                //for a suffix of t from j...n-1, i is the smallest \n                //index in s such that it is a subsequence\n                j--; \n            }\n        }\n\n        int ans = m; \n        for (int i = 0; i < m; ++i) { \n            //update answer for prefix/suffix is removed \n            //only (new t is a prefix or suffix of t)\n            if (l[i] != -1) ans = min(ans, m-i-1); \n            if (r[i] != -1) ans = min(ans, i); \n        }\n\n        //if the smallest suffix is invalid, we return our answer\n        //in order to avoid annoying casework in our binary search\n        if (r[m-1] == -1) return ans; \n        \n        for (int i = 0; i < m-1; ++i) {\n            if (l[i] != -1) {\n                if (l[i] >= r[m-1]) break; \n                \n                int lo = i + 1, hi = m - 1; \n                while (lo < hi) {\n                    int md = lo + (hi - lo)/2; \n                    //check if left index in s is less than right \n                    //index of the suffix (a < b as said in solution)\n                    if (l[i] < r[md]) hi = md; \n                    else lo = md + 1; \n                }\n                //lo is the smallest index in the biggest \n                //suffix that satisfies the condition \n                ans = min(ans, lo - i - 1); \n                //lo - i - 1 is the size if the deleted substring\n            }\n        }\n        return ans; \n        \n    }\n};\n```
['C++']