Binary Search + Sliding Window
We need to minimize something, so we naturally think of 3 possible methods\n1. Dp\n2. Greedy\n3. Binary Search the answer\n\nTrying the first 2 options I couldn
We need to minimize something, so we naturally think of 3 possible methods\n1. Dp\n2. Greedy\n3. Binary Search the answer\n\nTrying the first 2 options I couldn\'t figure a way to solve this problem,  So tried binary search search the answer (the length of deleted subarray of t string).\n\nCreate a function `check(int len)` which will return true if a subarray of len is deleted from t and t becomes a subsequence of s. false otherwise\n\nWe can use sliding window to solve create this function\n\n1. Lets assume we delete subarray of len from right hand side of t. Let int[] pos store the greedily matched positions of t from index 0 to t.length()-len.\n2. Now, keep on increasing the right subarray length till the deleted subarray becomes 0 to len-1. The transition of windows is same as previous, just greedily match the characters of s and t.\n\n\n```\npublic class Solution {\n    public int minimumScore(String S, String T) {\n        char[] s = S.toCharArray(), t = T.toCharArray();\n        int lo=0,hi=T.length();\n        while(lo<=hi){\n            int m = (lo+hi)>>1;\n            if(check(s,t,m)) hi = m-1;\n            else lo = m+1;\n        }\n        return hi+1;\n    }\n    private boolean check(char[] s, char[] t,int len){\n        int t_length = t.length,n=s.length;\n        if(len>=t_length) return true; //delete whole t array\n        int[] pos = new int[t_length]; //Greedy left matching\n        Arrays.fill(pos,1_000_000_0);\n        int t_left_index = 0;\n        for(int 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        int right_index_of_s =n-1;\n        for(int 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            int 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```
[]