binary search
Intuition\n Describe your first thoughts on how to solve this problem. \nfor a particular score , instead of removing just some elements b/w l and r. we can rem
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nfor a particular score , instead of removing just some elements b/w l and r. we can remove all the elements. that way we have to check for less number of elements of t for exactly the same score.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nwe binary search for a particular score and for all the values of l and r for this score. we check if t(0.........l-1) and t(r+1.......n-1) is a subsequence of s. if yes, then for this score, there exists a configuration where t is a subsequence of s. now we search for lower scores, otherwise we search for higher scores. to check for a paricular score, i used the prefix/suffix array and sliding window method.\n\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(nlogn)\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(n)\n\n# Code\n```\nclass Solution {\npublic:\n    vector<int>pref, suff;\n    bool can(int mid, string &t, string &s){\n        //cout<<mid<<endl;\n        for(int i=0, j=mid-1; j<t.size(); i++,j++){\n            int a= (i==0)?0:pref[i-1];\n            int b=(j==t.size()-1)?0:suff[j+1];\n            //cout<<i<<"   "<<j<<"    "<<a<<"    "<<b<<endl;\n            if(a==-1 || b==-1)continue;\n            if(a<b)return true;\n            if(j==t.size()-1 && a>=0)return true;\n            if(i==0 && b>=0)return true;\n        }\n        return false;\n    }\n    void precompute(string &s, string &t){\n        pref.resize(t.size(), -1);\n        suff.resize(t.size(), -1);\n        int n=s.size();\n        for(int i=0, j=0; i<n && j<t.size(); i++){\n            if(s[i]==t[j]){\n                pref[j]=i;\n                j++;\n            }\n        }\n        for(int i=n-1, j=t.size()-1; i>=0 && j>=0; i--){\n            if(s[i]==t[j]){\n                suff[j]=i;\n                j--;\n            }\n        }\n        // for(int i=0; i<t.size(); i++){\n        //     cout<<pref[i]<<"    "<<suff[i]<<endl;\n        // }\n    }\n    int minimumScore(string s, string t) {\n        precompute(s, t);\n        if(suff[0]!=-1)return 0;\n        int n=t.size();\n        int lo=1, hi=n;\n        while(hi-lo>1){\n            int mid=(hi+lo)/2;\n            bool c=can(mid, t, s);\n            if(c){\n                hi=mid;\n            }else{\n                lo=mid+1;\n            }\n        }\n        if(can(lo, t, s))return lo;\n        return hi;\n    }\n};\n```
['Binary Search', 'C++']