---
# System prepended metadata

title: 2565. Subsequence With the Minimum Score
tags: [Leetcode, Two Pointers, Hard]

---

# 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```

```t[i:]```是```s[dp[i]:]```的subsequence 负责suffix部分
接着我们看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
```java=
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;
    }
}
```