Find the Shortest Substring of t: Match from Right then Left, Two Pass, O(N)
Intuition \nThe score right - left + 1 equals to substring length.\nSo to minimize the score, it means we should find a shortest substring of t which after we r
# Intuition \nThe score `right - left + 1` equals to substring length.\nSo to minimize the score, it means we should find a shortest substring of `t` which after we remove this substring then `t` will be a subsequence of `s`.\n\n# Approach\nIf we match from first character of `t`, say `t[0:j+1]` is a subsequence of `s[0:i+1]`, then how many characters the rest of `s`, i.e. `s[i+1:]` can match `t` from t\'s right most? We can pre-calculate this right-match-cnt of `t`.\n\n# Complexity\n- Time complexity: O(N)\n- Space complexity: O(N)\n\n# Code\n```python3 []\nclass Solution:\n    def minimumScore(self, s: str, t: str) -> int:\n        ns = len(s)\n        nt = len(t)\n        rcnt = [0] * (ns + 1)  # right-match-cnt\n\n        i = ns - 1\n        j = nt - 1\n        while i >= 0:\n            if j >= 0 and s[i] == t[j]:\n                rcnt[i] = rcnt[i + 1] + 1\n                j -= 1\n            else:\n                rcnt[i] = rcnt[i + 1]\n            i -= 1\n\n        if rcnt[0] >= nt:  # match all of t\n            return 0\n\n        ret = nt - rcnt[0]\n        i = j = 0\n        while j < nt:\n            while i < ns and s[i] != t[j]:\n                i += 1\n            if i >= ns:\n                break\n            subret = nt - (rcnt[i + 1] + j + 1)  # left matches j+1, right matches rcnt[i + 1]\n            ret = min(ret, subret)\n            j += 1\n            i += 1\n        return ret\n```\n```C++ []\nclass Solution {\npublic:\n    int minimumScore(string s, string t) {\n        int ns = s.size(), nt = t.size();\n        vector<int> rcnt(ns + 1);\n        for (int i = ns - 1, j = nt - 1; i >= 0; --i) {\n            if (j >= 0 && s[i] == t[j]) {\n                rcnt[i] = rcnt[i+1] + 1;\n                --j;\n            } else {\n                rcnt[i] = rcnt[i+1];\n            }\n        }\n\n        if (rcnt[0] >= nt) return 0;\n\n        int ret = nt - rcnt[0];\n        for (int i = 0, j = 0; j < nt; ++j, ++i) {\n            while (i < ns && s[i] != t[j]) ++i;\n            if (i >= ns) break;\n            int subret = nt - (rcnt[i + 1] + j + 1);\n            ret = min(ret, subret);\n        }\n        return ret;\n    }\n};\n```\n```Java []\nclass Solution {\n    public int minimumScore(String s, String t) {\n        int ns = s.length(), nt = t.length();\n        int[] rcnt = new int[ns + 1];\n        for (int i = ns - 1, j = nt - 1; i >= 0; --i) {\n            if (j >= 0 && s.charAt(i) == t.charAt(j)) {\n                rcnt[i] = rcnt[i + 1] + 1;\n                --j;\n            } else {\n                rcnt[i] = rcnt[i + 1];\n            }\n        }\n        if (rcnt[0] >= nt) return 0;\n\n        int ret = nt - rcnt[0];\n        for (int i = 0, j = 0; j < nt; ++i, ++j) {\n            while (i < ns && s.charAt(i) != t.charAt(j)) ++i;\n            if (i >= ns) break;\n            int subret = nt - (rcnt[i + 1] + j + 1);\n            ret = Math.min(ret, subret);\n        }\n        return ret;\n    }\n}\n```\n```Go []\nfunc minimumScore(s string, t string) int {\n    ns, nt := len(s), len(t)\n    rcnt := make([]int, ns + 1)\n    for i, j := ns - 1, nt - 1; i >= 0; i-- {\n        if (j >= 0 && s[i] == t[j]) {\n            rcnt[i] = rcnt[i + 1] + 1\n            j--\n        } else {\n            rcnt[i] = rcnt[i + 1]\n        }\n    }\n    if rcnt[0] >= nt {\n        return 0\n    }\n    ret := nt - rcnt[0]\n    for i, j := 0, 0; j < nt; i, j = i + 1, j + 1 {\n        for i < ns && s[i] != t[j] {\n            i++\n        }\n        if i >= ns {\n            break\n        }\n        if subret := nt - (rcnt[i + 1] + j + 1); subret < ret {\n            ret = subret\n        }\n    }\n    return ret\n}\n```\n
['C++', 'Java', 'Go', 'Python3']