很妙的题目。
首先考虑字典序最大的子序列有什么性质,很明显必须是非递增的,不然一定可以找到更大的子序列。
然后我们还可以发现令一个性质,假设我们现在的子序列是zabc
,我们经过一次变换之后会变为czab
,我们可以发现不管在其他字符是什么的情况下,zab
一定是最大的。大家可以思考一下为什么。
所以说,我们可以发现,我们经过这些变换之后,一定可以从降序变为一个升序的序列。所以,如果变为原来的最大子序列升序序列之后满足整个字符串是升序的,那么输出最大子序列的大小-最大字符的数量
,否则输出-1
鹅