Prefix array + suffix array || Binary Search || O( n log n) || C++
Intuition\n Describe your first thoughts on how to solve this problem. \nIf you will visualise you will find that character between right and left of deleted ch
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nIf you will visualise you will find that character between **right** and **left** of deleted charactes of \'t\' are useless ,it is better to consider them then as deleted as they will not effect the score .\n\nNow Problem statement changes **Find the smallest substring that can be deleted from t** such that **t become subsequence of s** . \n# Approach\n<!-- Describe your approach to solving the problem. -->\nI created two arrays prefix which store the index of \'s\' which matches with jth prefix character of \'t\' , similarly a suffix array .\n\nNow I want ot find max length disjoint set of prefix and suffix which minimise my value /score.\n\nSo For each of **prefix value** I consider I find the **smallest index with value just greater than prefix[i]** in **suffix** array , this will give me length of suffix that is disjoint or from [pref[i]+1,m-1] . \nm = length of t\nThe score is ((index-1) - (pref[i]+1) )+ 1 . \nIndex is the smallest value > than pref[i] , I delete all the elements from (prefix[i]+1 tot index-1) . I find score for each prefix \'i\' and store the minimum value.\n\n-- Consider the case when we don\'t take any prefix value.\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(n log n)\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(n)\n# Code\n```\n\nclass Solution {\npublic:\n    /*\n    I will delete a substring from t such that  prefix of of t before substring and suffix of t after substring\n    is a subsequency of s\n    */\n    int search(vector<int>&A,int value){\n        int start = 0,end = A.size()-1,mid = (start+end)/2;\n        int ans = -1;\n        while(start<=end){\n            //find the smallest element greater than value  \n            //I want to find max_suffix that is subsequence of \'s\' from [value+1 , t.size()-1]\n            if(A[mid] > value){\n                ans = mid;\n                end = mid-1;\n                mid = (start+end)/2;\n            }\n            else{\n                start = mid+1;\n                mid = (start+end)/2;\n            }\n        }\n        return ans;\n    }\n    \n    \n    int minimumScore(string s, string t) {\n        int n = s.size();\n        int m = t.size();\n         int start = 0,end = m-1;\n        vector<int>pref,suff;\n        int i =0 ,j = 0;\n\n        //find prefix array which store the index of \'s\'\n        //which matches with jth prefix character of t\n        while(i<n && j<m){\n            if(s[i] == t[j]){\n                pref.push_back(i);\n                start = j;\n                j++;\n            }\n            i++;\n        }\n        \n        i = n-1,j = m-1;\n        //similarly find suffix array which store the index of \'s\'\n        //which matches jth character of t\n        while(i>=0 && j>=0){\n            if(s[i] == t[j]){\n                suff.push_back(i);\n                end = j;\n                j--;\n            }\n            i--;\n        }\n        if(end == 0)return 0;\n        reverse(suff.begin(),suff.end());\n         //sort the suffix array in increasing order\n        int ans = m;\n\n        //we find score in case we delete a prefix from 0 to suff[0]-1\n        if(suff.size()){\n            int len = suff.size();\n            ans = min(ans,(m-len));\n        }\n        \n        for(int i=0;i<pref.size();++i){\n             //for each prefix character we consider\n             //we want to find the size of matching suffix \n             //from [pref[i+1] , m-1]\n            int idx = search(suff,pref[i]);\n            \n            //we consider the case when we delete suffix from [pref[i],m-1]\n            ans = min(ans,m-(i+1));\n            if(idx != -1){\n                int last = m - (suff.size() - idx);\n                \n                last--;\n                \n                ans = min(ans,(last - (i+1))+1);\n            }\n            \n        }\n        \n        //cout<<"\\n";\n        \n        return ans;\n    }\n};\n```
['C++']