2193-得到回文串的最少操作次数

给你一个只包含小写英文字母的字符串 s 。

每一次操作，你可以选择 s 中两个相邻的字符，并将它们交换。

请你返回将 s 变成回文串的 最少操作次数 。

注意，输入数据会确保 s 一定能变成一个回文串。

示例 1：

**输入：** s = "aabb"
**输出：** 2
**解释：**
我们可以将 s 变成 2 个回文串，"abba" 和 "baab" 。
- 我们可以通过 2 次操作得到 "abba" ："a _ **ab**_ b" -> "ab _ **ab**_ " -> "abba" 。
- 我们可以通过 2 次操作得到 "baab" ："a _ **ab**_ b" -> " _ **ab**_ ab" -> "baab" 。
因此，得到回文串的最少总操作次数为 2 。

示例 2：

**输入：** s = "letelt"
**输出：** 2
**解释：**
通过 2 次操作从 s 能得到回文串 "lettel" 。
其中一种方法是："lete _ **lt**_ " -> "let _ **et**_ l" -> "lettel" 。
其他回文串比方说 "tleelt" 也可以通过 2 次操作得到。
可以证明少于 2 次操作，无法得到回文串。

提示：

1 <= s.length <= 2000
s 只包含小写英文字母。
s 可以通过有限次操作得到一个回文串。

解法：贪心

经典的题目。

由于题目保证原串一定可以变成回文串，那么原串中最多只有一种字母出现奇数次。如果有一种字母出现奇数次，那么将该字母中排在最中间的字符移动到字符串中间，剩下的字符可以转化为所有字母均出现偶数次的情况。

贪心算法是：每次固定字符串最左边的字母 a 不变，找出距离字符串右侧最近的 a，把它交换到字符串最右边。这样字符串的头尾字母就相等了。把字符串的头尾去掉，就变成了子问题。把所有子问题的答案加起来就是最少交换次数。

由于数据范围较小，通过 \mathcal{O}(n^2) 的模拟即可通过本题。

证明

构造回文串的过程，实际上是每次选择一对字母并把它们交换到字符串头尾的过程。考虑字母 x 和字母 y 哪个先选，分以下情况讨论：

字母 x 和 y 的位置满足 \underbrace{\cdots}{a\text{ 个字母} }x\underbrace{\cdots}{b\text{ 个字母} }y\underbrace{\cdots}{c\text{ 个字母} }y\underbrace{\cdots}{d\text{ 个字母} }x\underbrace{\cdots}_{e\text{ 个字母}。如果先把 x 换到头尾，再把 y 换到头尾，那么需要 (a + e) + (b + d) 次交换；如果先换 y 再换 x，那么需要 (a + b + 1 + d + e + 1) + (a + e) 次交换。显然先换 x 更优。
字母 x 和 y 的位置满足 \underbrace{\cdots}{a\text{ 个字母} }x\underbrace{\cdots}{b\text{ 个字母} }y\underbrace{\cdots}{c\text{ 个字母} }x\underbrace{\cdots}{d\text{ 个字母} }y\underbrace{\cdots}_{e\text{ 个字母}。如果先换 x 再换 y，那么需要 (a + d + e + 1) + (a + b + e) 次交换；如果先换 y 再换 x，那么需要 (a + b + 1 + e) + (a + d + e) 次交换。先换哪个都一样。
字母 x 和 y 的位置满足 \underbrace{\cdots}{a\text{ 个字母} }x\underbrace{\cdots}{b\text{ 个字母} }x\underbrace{\cdots}{c\text{ 个字母} }y\underbrace{\cdots}{d\text{ 个字母} }y\underbrace{\cdots}_{e\text{ 个字母}。如果先换 x 再换 y，那么需要 (a + c + d + e + 2) + (a + b + c + e) 次交换；如果先换 y 再换 x，那么需要 (a + b + c + 2 + e) + (a + c + d + e) 次交换。先换哪个都一样。

上述讨论可以得到结论：每次交换最外边出现的字母不劣。因此贪心解法成立。

参考代码（c++）

class Solution {
public:
    int minMovesToMakePalindrome(string s) {
        int n = s.size(), ans = 0;
        for (int i = 0, j = n - 1; i < j; i++) {
            for (int k = j; i != k; k--) if (s[i] == s[k]) {
                // 字母出现偶数次的情况，模拟交换
                for (; k < j; k++) swap(s[k], s[k + 1]), ans++;
                j--;
                goto OK;
            }
            // 字母出现奇数次的情况，计算它距离中间还有多少距离
            ans += n / 2 - i;
            OK: continue;
        }
        return ans;
    }
};