Minimum Subarray Deletion to Form a Subsequence
Intuition\nThe problem statement mentions finding the minimum length of a subarray of one string (S) that needs to be deleted to make it a subsequence of anothe
# Intuition\nThe problem statement mentions finding the minimum length of a subarray of one string (S) that needs to be deleted to make it a subsequence of another string (T).\n\nOne approach to solve this problem is to use binary search. We can start with the length of T as the upper limit and 0 as the lower limit. In each iteration of binary search, we check if a subarray of length m (the midpoint of the current lower and upper limits) can be deleted from S to make it a subsequence of T.\n\nTo check if a subarray of length m can be deleted, we can use two pointers to traverse both the arrays S and T. We can use the first pointer to traverse T and keep track of the positions of each character of T in S. Then, we use the second pointer to traverse S in reverse and check if the subarray of length m can be deleted such that T remains a subsequence of S.\n\nBased on the result of the check, we can adjust the lower and upper limits of binary search accordingly and continue the search until the lower limit is greater than the upper limit.\n\nThe final answer would be hi + 1, where hi is the upper limit after the binary search.\n\n# Approach\nThe algorithm is a binary search solution for finding the minimum length of a subarray of one string that needs to be deleted to make it an subsequence of another string.\n\n# Complexity\n- Time complexity:\nThe time complexity of this algorithm is O(n log n), where n is the length of the string T.\n\nThe binary search portion of the algorithm takes O(log n) time for each iteration, and the check function takes O(n) time, so the overall time complexity is O(n log n).\n\n- Space complexity:\nThe space complexity of this algorithm is O(n).\n\nThe main source of space consumption in this algorithm is the pos array, which stores the positions of characters of T in S. The size of this array is n, where n is the length of T, so the space complexity is O(n).\n\n# Code\n```\n/**\n * @param {string} s\n * @param {string} t\n * @return {number}\n */\nvar minimumScore = function(S, T) {\n    let s = S.split(\'\'), t = T.split(\'\');\n    let lo = 0, hi = T.length;\n    while (lo <= hi) {\n        let m = Math.floor((lo + hi) / 2);\n        if (check(s, t, m)) hi = m - 1;\n        else lo = m + 1;\n    }\n    return hi + 1;\n};\n\nvar check = function(s, t, len) {\n    let t_length = t.length, n = s.length;\n    if (len >= t_length) return true; //delete whole t array\n    let pos = new Array(t_length).fill(1000000000); //Greedy left matching\n    let t_left_index = 0;\n    for (let i = 0; i < n; i++) {\n        if (t_left_index === t_length) break;\n        if (t[t_left_index] === s[i]) {\n            pos[t_left_index] = i;\n            t_left_index++;\n        }\n    }\n    if (t_left_index >= t_length - len) return true; //we can delete right subarray of length len\n    let right_index_of_s = n - 1;\n    for (let rp = t_length - 1; rp >= len; rp--) {\n        while (right_index_of_s >= 0 && s[right_index_of_s] !== t[rp]) right_index_of_s--;\n        if (right_index_of_s === -1) return false;\n        let lp = rp - len - 1;\n        if (lp === -1 || pos[lp] < right_index_of_s) return true;\n        right_index_of_s--;\n    }\n    return false;\n};\n\n\n```
['JavaScript']