我们发现，在 为回文串时，会有 对 满足 ，即 的价值为 。可以证明这是最大价值。
我们发现，在字符串 中，满足 的 有且只有 对。在此之上要同时满足 ，构造一个回文串便能保持价值为 。
证毕。
所以构造一个回文串即可。注意同一字符不能出现超过两次。
暂无评论