《Composition》题目分析

本题最暴力的解法就是枚举哪些字符被删掉。枚举的复杂度是O(2^N)，再加上O(N)的判断，总复杂度是O(N2^N)。

比较容易想到的是O(N^2)的DP。

由于删掉最少等价于留下最多，所以我们可以用f[i]表示最后留下一个字符是S[i]时，最多留下多少个字符。

要求f[i]，我们只需要枚举S[i]之前的一个字符是哪个，并且从中选择合法并且最优的解：

f[i] = max{f[j]} + 1, for j = 1 .. i-1且S[j]S[i]不是"illegal pair"。

以上的DP解法是O(N^2)的，仍有优化的空间。

我们求f[i]时，需要枚举之前所有的位置j，但实际上之前的字符只有'a'~'z'26种可能。对于相同的字符，我们只用考虑最后一次它出现的位置，之前的位置一定不是最优。

例如，假设s[2] = s[5] = s[8] = 'h'，那么当i>8时，我们求f[i]根本不用考虑j=2和j=5的情况，这两种情况即便合法也不会比j=8更优。

于是我们每次求f[i]只需要考虑'a'~'z'最后一次出现的位置。复杂度可以优化到O(26N)。