# 2565. Subsequence With the Minimum Score
###### tags: `Leetcode` `Hard` `Two Pointers`
Link: https://leetcode.com/problems/subsequence-with-the-minimum-score/description/
## 思路
思路参考[这里](https://leetcode.com/problems/subsequence-with-the-minimum-score/solutions/3174041/right-and-left-o-n/)
因为要让最后一个删掉的character的index第一个删掉的character的index最小
那么我们就要尽可能保留t的prefix和suffix
所以我们需要找到最长的prefix + suffix of ```t``` that is a subsequence of ```s```

接着我们看prefix部分
如果```t[0:j+1]```是```s[0:i+1]```的subsequence 并且能在dp array里面找到一个值大于等于```j+1``` 那说明对于现在的prefix of ```t``` 存在一个suffix of ```t```能让两个合在一起是```s```的subsequence
找的过程我们可以用two pointers实现 因为每次往右挪动```i``` dp array对应的位置只可能保持不变或者往右

## Code

class Solution {
public int minimumScore(String s, String t) {
int m = s.length(), n = t.length(), k = n - 1;
int[] dp = new int[n];
Arrays.fill(dp, -1);
for (int i = m - 1; i >= 0 && k >= 0; --i)
if (s.charAt(i) == t.charAt(k))
dp[k--] = i;
int res = k + 1;
for (int i = 0, j = 0; i < m && j < n && res > 0; ++i)
if (s.charAt(i) == t.charAt(j)) {
while(k<n && dp[k]<=i) k++;
res = Math.min(res, k - (++j));
}
return res;
}
}