O(N) left match and right match, easy to understand C++
The key idea is if we fix the min (left) idex to remove,  how to find the min right idex as the last characater to be removed.\nWe can do this by the following 
The key idea is if we fix the min (left) idex to remove,  how to find the min right idex as the last characater to be removed.\nWe can do this by the following step:\n1 Calculate the left first match, and store the min match index in a deque (vector should be fine also).\n2 Calculate the right first match, and store the max match index in a deque.\n3 For each element in the left match deque, if we use it as last index on left,  then indices less or equal to it in the right match deque are invalid, should be pop out. And the rest in right deque is the max match on right side we can have.\n4 When we iterate over left deque, we get all possible left and right. Notice that if the left or right match deque has a size same as t, the answer is 0.\n\nThe time and space complexity is O(N).\n\t\n\t\n\tclass Solution {\n\tpublic:\n\t\tint minimumScore(string s, string t) {\n\t\t\tint n = s.size();\n\t\t\tint m = t.size();\n\t\t\tdeque<int> rmatch;\n\t\t\tint si = n - 1;\n\t\t\tint ti = m - 1;\n\t\t\twhile(si >= 0 && ti >= 0){\n\t\t\t\twhile(si >= 0 && ti >= 0 && s[si] == t[ti]){\n\t\t\t\t\trmatch.push_front(si);\n\t\t\t\t\tsi--;\n\t\t\t\t\tti--;\n\t\t\t\t}\n\t\t\t\tsi--;\n\t\t\t}\n\t\t\tdeque<int> lmatch;\n\t\t\tsi = 0;\n\t\t\tti = 0;\n\t\t\twhile(si < n && ti < m){\n\t\t\t\twhile(si < n && ti < m && s[si] == t[ti]){\n\t\t\t\t\tlmatch.push_back(si);\n\t\t\t\t\tsi++;\n\t\t\t\t\tti++;\n\t\t\t\t}\n\t\t\t\tsi++;\n\t\t\t}\n\t\t\tif(lmatch.size() == m) return 0;\n\t\t\tint ans = min(m, m - (int)rmatch.size());\n\t\t\tfor(int i = 0; i < lmatch.size(); i++){\n\t\t\t\tint left = i + 1;\n\t\t\t\twhile(!rmatch.empty() && rmatch.front() <= lmatch[i]){\n\t\t\t\t\trmatch.pop_front();\n\t\t\t\t} \n\t\t\t\tint right = m - 1 - rmatch.size();\n\t\t\t\tans = min(ans, right - left + 1);\n\t\t\t}\n\t\t\treturn ans;\n\t\t}\n\t};
[]