C++, right left, 3 loops, O(n)
got idea from votrubac (https://leetcode.com/problems/subsequence-with-the-minimum-score/discuss/3174041/Right-and-Left-O(n)) and qeetcode sol in weekly contest
got idea from votrubac (https://leetcode.com/problems/subsequence-with-the-minimum-score/discuss/3174041/Right-and-Left-O(n)) and qeetcode sol in weekly contest 332 (https://leetcode.com/qeetcode/).\nIt can be done in only two for loops with O(n) time complexity but use three here because it is easier to understand.\n\nIn the problem hint, dp array based on t is recommended. However, it is complicated when determine whether prefix and surfix overlap in s.  Therefore, dp array based on s is chosen here.\n\nuse two array left[ns] and right[ns] with size of s string.\nleft[i] stands for max prefix length of t that is a subsequence of substring from s[0] to s[i] (including s[i]);\nright[i] stands for max surfix length of t that is a subsequence of substring from s[i] to s[ns-1] (including s[i]).\n\nthe minimum score is initialized as min(left[ns-1], right[0]), which is the prefix only and surfix only case.\nminimum score = min of nt-left[i]-right[i+1].\nif the minimum value is smaller than 0, return 0.\n  \n```\nclass Solution {\npublic:\n    int minimumScore(string s, string t) {\n        int ns=s.size(), nt=t.size();\n        vector<int> left(ns), right(ns);\n        for(int i=0, j=0; i<ns; i++) {\n            if(j<nt && s[i]==t[j])\n                j++;\n            left[i]=j;\n        }\n        for(int i=ns-1, j=0; i>=0; i--) {\n            if(j<nt && s[i]==t[nt-1-j])\n                j++;\n            right[i]=j;\n        }\n        int res=min(nt-left[ns-1], nt-right[0]);\n        for(int i=0; i<ns-1; i++) {\n            res=min(res, nt-left[i]-right[i+1]);\n        }\n        return max(res, 0);\n    }\n};\n```
['C']