solution
答案等于 压栈次数 ×2+n×2+n ,于是只需最小化压栈次数.
观察栈的形态,可以发现两条性质.
- 栈中相邻的两个元素不可能相等.
- 如果当前字符与栈顶下面一个字符相等,弹栈一定不会劣于压栈,于是栈中隔一个也不会相等.
第一个性质很好理解，第二个呢？
举个例子就好，
压入栈的可能以后用不到，到后来还会弹出
弹出栈的以后用不到，则这个弹出操作就赚了呗
如果以后会用到（第一个性质已经解决了多个相连相等的情况）,
压栈的还会弹到这，弹栈的还会压到这，两者消耗是一样的(不是指严格的消耗)
如果实在不懂就感性理解一下，还是很好想的
综合来看弹栈一定不会劣于压栈,于是栈中隔一个也不会相等
而字符集的大小为 3 ,所以栈中元素一定形如 …ABCABCA… ,状态数是 O(|S|)的.
dp 记录当前打印到了哪个字符以及栈的形态,转移是 O(1) 的,所以时间复杂度为 $O(|S|^2)$ .
总结：
本题关键就在于只有三个字符，导致了第二个性质的诞生
solution：
考虑 hash ,先算出n 个排列各自的 hash 值,排序后再hash 起来.
只需要快速计算一个排列按照题意操作后得到的 n个排列的 hash 值.即可On判断是否成立
可以算出原排列的 hash值后,考虑删掉每个数各自会带来的贡献即可维护