Video Explanation(Hindi) ||  O(n) || Prefix and Suffix array  || C++
Video Explanation ( Hindi )\n# Intuition\n Describe your first thoughts on how to solve this problem. \nIf you will carefully observe ,the score depends on the 
[Video Explanation ( Hindi )](https://www.youtube.com/watch?v=-BlFzx80flA&t=912s)\n# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nIf you will carefully observe ,the score depends on the (**maximum and minium index** ) deleted and any **other index between** is **useless** ,  so its better to consider or delete all of them . Then (right - left)+1 = length of substring deleted .\nAnd now you know the main **hidden** problem , **Find the minimum length of substring which when deleted makes t subsequency of s** .\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nHere the string \'s\' does not change and after removing substring from \'t\' our t is divided into two parts suffix( part after delted substring to end) and prefix (part from start to just before delted substring) . \nWe can form two disjoint parts from [0,i] and [i+1, n-1] for each index \'i\' , n = length of string \'s\' . And for [0,i] we want to find the max length of prefix that we can get from [0,i] characters of \'s\' and for [i+1,n-1] we want to find the length of max suffix of \'t\' that we can get .\n\nLet x = max_prefix_length (for [0,i])\ny = max_suffix_length ( for [i+1,n-1])\nm = intial length of string \'t\'\nlen = length of string formed from prefix and sufix for \'i\' = (x+y)\nLenth of substring deleted  = m - len \nWe find len for each of the \'i\' and store the minmum .\nEdge case when we derive just prefix or suffix from whole string s.\n\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(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    \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(n),suff(n);\n        int i =0 ,j = 0;\n\n        //prefix[i] store the max lenght of prefix of array that can be derived\n        //from characters of string \'S\' from [0,i]\n        int c = 0;\n        while(i<n && j<m){\n            if(s[i] == t[j]){\n                c++;\n                j++;\n            }\n            pref[i] = c;\n            i++;\n        }\n        while(i<n){\n            pref[i] = c;\n            i++;\n        }\n        // length of substring to remove if we derive prefix from [0,n-1] of \n        //character of \'S\'\n        int ans = m-c;\n        i = n-1,j = m-1;\n         c = 0;\n\n        //suffix[i] store the max lenght of prefix of array that can be derived\n        //from characters of string \'S\' from [i,n-1]\n        while(i>=0 && j>=0){\n            if(s[i] == t[j]){\n                c++;\n                j--;\n            }\n            suff[i] = c;\n            i--;\n        }\n        \n        while(i>=0){\n            suff[i] = c;\n            i--;\n        }\n        if(c == m)return 0;\n        \n        // length of substring to remove if we derive suffix from [0,n-1] of \n        //character of \'S\'\n        ans = min(m-c,ans);\n        for(int i=0;i<(n-1);++i){\n            //m - inital length of string \'t\'\n            // pref[i] + suff[i] = final length of string \'t\' after removing substring\n            ans = min(ans,m - (pref[i]+suff[i+1]));\n        }\n        \n        return ans;\n    }\n};\n```
['Suffix Array', 'Prefix Sum', 'C++']