Readme

2565.Subsequence-With-the-Minimum-Score

本题的题意有点文字游戏。本质上，left到right之间的字符不删白不删，删的越多t就越容易成为s的subsequence。所以本题就是在t字符串里找一段可删除的最短substring，使得t成为s的subsequence。

于是，t其实就分成了三部分：xxx yyy zzz，第二部分是需要删除的，第一部分和第三部分拼接起来是s的一个subsequence。这等价于xxx必须是s的一个前缀的subsequence，而zzz必须是s的一个后缀的subsequence，且s的前缀和后缀不能重合。我们发现这部分信息其实是可以提前处理的，我们可以从前往后扫一遍，计算left[i]表示s的最短前缀长度是多少，使得其能包含t[0:i]，即t[0:i]是该前缀的subsequence。同理，从后往前扫一遍，可以计算right[i]表示s的最短后缀长度是多少，使得其能包含t[i:n-1]，即t[0:n-1]是该后缀的subsequence。

根据套路，考虑到t分成了三部分，我们不妨遍历中间的部分，然后利用第一部分和第三部分的已知信息。假设中间yyy的部分是[i:j]，那么我们如果left[i-1] < right[j+1]的话，我们就可以知道t[0:i-1]+t[j+1:n-1]拼接起来就是s的subsequence了。

那么如何遍历中间部分呢？如果知道了yyy的长度，那么搞一个固定长度滑窗在t上走一遍即可。那么yyy的长度有哪些可能呢？其实只要二分搜索一下即可。因为有单调性的存在：yyy越长，必然就容易实现删除后的t是s的子序列；极端情况就是yyy部分占据了整个t，那么答案就是n，不过这不一定是最优解。所以我们试探减小yyy的长度，就可以逐步逼近最优解。