12ms | C++ | Sliding Window | Full Explanation
Approach\n Describe your approach to solving the problem. \n1. First thing to notice is that if I\'m chosing a score x where difference in leftmost deleted elem
# Approach\n<!-- Describe your approach to solving the problem. -->\n1. First thing to notice is that if I\'m chosing a score x where difference in leftmost deleted element and rightmost deleted element is x, why not delete this whole substring as it will reduce the no. of matches needed and also doesn\'t affect the score.\n2. Store prefix and suffix arrays which keeps the minimum index in s for a subsequence match of prefix and suffix of t.\n    For ex - \n    s: babacabca\n    t: bbc\n\n    pre = {0, 2, 4}\n    suf = {2, 6, 7}\n3. Binary Search for a given score if it\'s possible to get a score of x.\n4. Checking if it is possible to remove x no. of elements in such a way that the prefix + suffix is a subsequence of the other string.\n    012---678 (deleting indexes 3-5)\n    using pre[2] < suf[6]\n\n# Complexity\n- Time complexity:\nO(nlogn)\nCan be done in O(n) by using suffix on s and prefix on t.\n\n- Space complexity:\nO(n)\n\n# Code\n```\nclass Solution {\npublic:\n    int n, m;\n    \n    bool pos_to_mch(int mid, vector<int> &pre, vector<int> &suf){\n        if (mid == 0) return pre[m-1] < n;\n        else if (mid == m) return true;\n        \n        // first #mid characters || last #mid characters\n        if (suf[mid] >= 0 || pre[m-1-mid] < n) \n            return true;\n        \n        // Deleting #mid character starting from index i\n        for (int i=1; i+mid<m; i++){\n            if (pre[i-1] < suf[i+mid]) \n                return true;\n        }\n        return false;\n    }\n    \n    int minimumScore(string s, string t) {\n        n = s.size();\n        m = t.size();\n        \n        vector<int> pre_mch(m);\n        vector<int> suf_mch(m);\n        \n        int cur = 0;\n        for (int i=0; i<m; i++){\n            while (cur < n && s[cur] != t[i]) \n                cur++;\n            pre_mch[i] = cur++;\n        }\n        \n        cur = n-1;\n        for (int i=m-1; i>=0; i--){\n            while (cur >= 0 && s[cur] != t[i]) \n                cur--;\n            suf_mch[i] = cur--;\n        }\n        \n        int low = 0, high = m;\n        \n        while(low <= high){\n            int mid = (low+high)/2;\n            if (pos_to_mch(mid, pre_mch, suf_mch))\n                high = mid-1;\n            else \n                low = mid+1;\n        }\n        return low;\n    }\n};\n```
['C++']