Two Pointer Dp Prefix Suffix O(n) Time Complexity
Intuition\n- We want to eliminate the characters which can not help in t string forming as subsequence.\n- But, we can also remove characters which can help \'t
# Intuition\n- We want to eliminate the characters which **can not help in t string forming as subsequence**.\n- But, we can also remove characters which can help \'t\' in forming substring.\n- ultimately the resultant string should be a subsequence that\'s it.\n- so, we use dp kind of approach.\n- The score formula if we observe carefully it is removal of **substring** from t.\n- By this we can say that if we know **prefix subsequence** and **suffix subsequence**, we can remove middle substring between those indices right.\n- Then out of all we will find **min substring length**.\n- Observe code for detailed explanation.\n- It\'s implementation is kind of tricky.\n\n# Complexity\n- Time complexity: $$O(n)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(n)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    int minimumScore(string s, string t) {\n        int n = s.length(),m = t.length();\n        //This suffix array is used as a dp kind of thing\n        //we are basically storing the suffix substring of \'t\'\n        //which matches with \'s\'\n        //subsequence means all the characters in \'t\' should be present in \'s\' right\n        //so we are storing till what index that suffix of \'t\' is\n        //present as subsequence\n        //if not default values are -1\n        vector<int> suffix(m,-1);\n        int i = n-1, j = m-1;\n        while(i >= 0 && j >= 0) {\n            while(i >= 0 && s[i] != t[j]) {\n                i--;\n            }\n            if(i < 0) break;\n            suffix[j] = i;\n            j--;\n            i--;\n        }\n        //after constructing the suffix array let\'s construct the prefix array in same manner.\n        i = 0,j = 0;\n        vector<int> prefix(m,-1);\n        while(i < n && j < m) {\n            while(i < n && s[i] != t[j]) {\n                i++;\n            }\n            if(i >= n) break;\n            prefix[j] = i;\n            i++;\n            j++;\n        }\n        //now let\'s jump to main code\n        //we have in our hands prefix and suffix arrays which basically\n        //represents subsequence index in \'s\'\n        //now let\'s take two pointers to iterate over respective arrays\n        int suf_ptr = 0,pref_ptr = 0;\n        \n        //now we know that suffix array initially contains \'-1\' as default means for that index in \'t\' we can form subsequence\n        while(suf_ptr < m && suffix[suf_ptr] == -1) suf_ptr++;\n        \n        //we took ans initially as starting index in suffix array which is not -1 becoz one possible result is we can delete all characters in \'t\' before suf_ptr right so that we can form subsequence\n        int ans = suf_ptr;\n\n        //if no \'-1\' is present then suf_ptr will point to starting index right, this means that whole string \'t\' is already a subsequence of \'s\' so return 0\n        if(suf_ptr == 0) return 0;\n        \n        //we need to get ans from all possible combinations of both prefix and suffix\n        //but prefix[pref_ptr] < suffix[suf_ptr] becoz we are actually deleting a substring between these both indices so that we can form a \'t\' as a subsequence of \'s\' so prefix should be less than suffix\n        while(pref_ptr < m && prefix[pref_ptr] != -1) {\n            //move suf_ptr if above mentioned condition is violated\n            while(suf_ptr < m && prefix[pref_ptr] >= suffix[suf_ptr]) {\n                suf_ptr++;\n            }\n            //update ans by below formula of removing between range substring\n            ans = min(ans, suf_ptr - pref_ptr - 1);\n            pref_ptr++;\n        }\n        //we might get another doubt that we are not exiting even when suf_ptr reaches m we keeping it as constant not incrementing it  observe above\n        //why?\n        //becoz we can only prefix and ignore suffix right\n        //so we also consider t.size as a index check that also\n        return ans;\n    }\n};\n```
['C++']