T3

30 分

暴力枚举交换的两个位置，然后 $\mathcal{O}(n)$ 计算最小代价，时间复杂度 $\mathcal{O}(n^3)$。

50 分

最小代价的计算显然可以优化，不需要每次重新计算，将交换的两个位置的代价重新计算即可，时间复杂度 $\mathcal{O}(n^2)$。

正解

$n$ 这么大显然是没用的，先用个桶统计一下 $(S_i,S_{n-i+1})$。

考虑没有那个交换操作怎么做，要成为回文串的话，两个对称位置上的字母 $x,y$，可以是 $x$ 变成 $y$ 也可以是 $y$ 变成 $x$，或者两个都变成另外一个字母 $z$，于是可以在 $\mathcal{O}(26^2)$ 下解决问题。

现在有了一个交换操作，但是并不需要真的去 $\mathcal{O}(n^2)$ 去枚举交换的位置，因为该交换操作最多只涉及到了两对对称位置上的字母，其他的都没有影响，于是直接 $\mathcal{O}(26^4)$ 去枚举涉及到的两对对称位置上的字母是什么就可以了。