Readme

1898.Maximum-Number-of-Removable-Characters

本题乍看还是很有难度的。本题的核心问题是：当字符串s刨掉k个字符之后，如何高效判定p还是s的subsequence?

我们先考虑，如果s不需要删除任何字符，那么判定p是否s的subsequence的方法是什么？这一点很关键，不要想歪到双序列DP（那是n^2的复杂度）。其实很简单，就是贪心法和双指针。考察每个p[j]，看是否有递增的i序列，满足s[i]==p[j]. 如果所有的p[j]都有了配对，那么p就是s的subsequence。

接下来我们考虑有字符删除的情况。此时，顺次考察i的时候，除了检查是否有s[i]与p[j]相等之外，还要关心这个相等的s[i]是否是被删除的k个元素之一。如果是的话，那么这个i就不和条件，需要继续往后找其他的i来与p[j]匹配。很显然，我们用一个hash表来提前存储两个信息：s[i]是否是removable序列里，如果在的话它是removable序列的第几个。特别注意，即使它在removable序列里，但是它在removalbe序列的index大于等于k，说明它并不是被删除的k个元素之一（因为被删除的序号是0到k-1），这样的s[i]依然是可以算作p的一部分。