[CLEAN] O(NlogN) to O(N)
O(NlogN)\n\nclass Solution {\npublic:\n    int minimumScore(string s, string t) {\n        int sl=s.size();\n        int tl=t.size();\n        vector<int> left(
O(NlogN)\n```\nclass Solution {\npublic:\n    int minimumScore(string s, string t) {\n        int sl=s.size();\n        int tl=t.size();\n        vector<int> left(tl,sl), right(tl,-1);\n        //s to unordered_map<c,<idx>>\n        unordered_map<char,vector<int>> m;\n        for(int x=0;x<sl;x++){\n            m[s[x]].push_back(x);\n        }\n        int bl=tl,br=tl;\n        //fill left\n        //O(NlogN)\n        int temp=-1;\n        for(int x=0;x<tl;x++){\n            vector<int> &v=m[t[x]];\n            int idx=upper_bound(v.begin(),v.end(),temp)-v.begin();\n            if(idx==v.size()){\n                bl=x;\n                break;}\n            temp=v[idx];\n            left[x]=temp;\n        }\n        //fill right\n        //O(NlogN)\n        temp=sl;\n        for(int x=tl-1;x>=0;x--){\n            vector<int> &v=m[t[x]];\n            int idx=-1*(upper_bound(v.rbegin(),v.rend(),temp,greater<int>())\n                -v.rend())-1;\n            if(idx==-1){\n                br=(tl-1)-x;\n                break;}\n            temp=v[idx];\n            right[x]=temp;\n        }\n        //get result\n        //O(NlogN)\n        int res=tl-max(bl,br);\n        if(res==0)\n            return 0;\n        for(int x=0;x<tl;x++){\n            int a=left[x];\n            if(a==sl)\n                break;\n            int idx=upper_bound(right.begin(),right.end(),a)-right.begin();\n            if(idx==tl)\n                break;\n            res=min(idx-x-1,res);\n        }\n        return res;\n    }\n};\n```\n\nO(N)\n```\nclass Solution {\npublic:\n    int minimumScore(string s, string t) {\n        int sl=s.size();\n        int tl=t.size();\n        vector<int> left(tl,sl), right(tl,-1);\n        \n        int bl=0,br=0;\n        //fill left\n        //O(N)\n        int temp=0;\n        for(int x=0;x<sl;x++){\n            if(s[x]==t[temp]){\n                left[temp]=x;\n                temp++;\n                bl++;\n            }\n            if(temp==tl)\n                break;\n        }\n        //fill right\n        //O(N)\n        temp=tl-1;\n        for(int x=sl-1;x>=0;x--){\n            if(s[x]==t[temp]){\n                right[temp]=x;\n                temp--;\n                br++;\n            }\n            if(temp<0)\n                break;\n        }\n        //get result\n        //O(N)\n        int res=tl-max(bl,br);\n        if(res==0)\n            return 0;\n        temp=0;\n        for(int x=0;x<tl;x++){\n            if(left[x]==sl)\n                break;\n            while(right[temp]<=left[x]){\n                temp++;\n                if(temp==tl)\n                    return res;\n            }\n            res=min(temp-x-1,res);\n        }\n        return res;\n    }\n};\n```
['Two Pointers', 'Binary Search', 'Greedy', 'C']