Prefix + Suffix Array + Binary Search Solution
Intuition\n Describe your first thoughts on how to solve this problem. \nS: Source string \nT: Target string (where we can do removal operation)\n\nWe have to f
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nS: Source string \nT: Target string (where we can do removal operation)\n\nWe have to find longest prefix and suffix of T that is a subsequence of S.\nWe have to do some operation on them (prefix and suffix array) to figure what elements will remain at end. We can get the removal length by subtracting this present length from length of T\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\nS: Source string \nT: Target string (where we can do removal operation)\n1. Find the longest prefix of T that is a subsequence of S\n2. Find the longest suffix of T that is a subsequence of S\n3. If the length of prefix = length of T, answer is 0 as no removal required\n4. Find the minimum overlap that can be eliminated. This can be achieved by binary search. We can iterate prefix array and search in suffix array the value greater than current value.\n5. We get present element length = length of prefix + length of suffix - overlap\n6. Cost = length of T - present length \n\n# Complexity\n- Time complexity: O(NlogN)\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```\nclass Solution {\npublic:\n    int minimumScore(string s, string t) {\n        vector<int> prefix, suffix;\n        \n        for(int i = 0, j = 0; i < s.length() and j < t.length(); i++) {\n            if(s[i] == t[j]) {\n                prefix.push_back(i);\n                j++;\n            }\n        }\n        \n        for(int i = s.length() - 1, j = t.length() - 1; 0 <= i and 0 <= j; i--) {\n            if(s[i] == t[j]) {\n                suffix.push_back(i);\n                j--;\n            }\n        }   \n        reverse(suffix.begin(), suffix.end());\n        \n        if(prefix.size() == t.length()) { // already a subsequence\n            return 0;\n        }\n        \n        int overlap = prefix.size();\n        for(int i = 0; i < prefix.size(); i++) {\n            // eliminated from prefix\n            int left = prefix.size() - i - 1;\n            // eliminated from suffix\n            int right = upper_bound(suffix.begin(), suffix.end(), prefix[i]) - suffix.begin();\n            // minimum elimination required for prefix_end < suffix_start\n            overlap = min(overlap, left + right);\n        }\n        \n        // elements present at the end\n        int present = prefix.size() + suffix.size() - overlap;\n        // elements eleminated or the cost\n        return t.length() - present;\n    }\n};\n```
['Binary Search', 'C++']