给你一个只包含小写英文字母的字符串 s 。
每一次 操作 ，你可以选择 s 中两个 相邻 的字符，并将它们交换。
请你返回将 s 变成回文串的 最少操作次数 。
注意 ，输入数据会确保 s 一定能变成一个回文串。
示例 1：
输入：s = "aabb" 输出：2 解释： 我们可以将 s 变成 2 个回文串，"abba" 和 "baab" 。 - 我们可以通过 2 次操作得到 "abba" ："aabb" -> "abab" -> "abba" 。 - 我们可以通过 2 次操作得到 "baab" ："aabb" -> "abab" -> "baab" 。 因此，得到回文串的最少总操作次数为 2 。
示例 2：
输入：s = "letelt" 输出：2 解释： 通过 2 次操作从 s 能得到回文串 "lettel" 。 其中一种方法是："letelt" -> "letetl" -> "lettel" 。 其他回文串比方说 "tleelt" 也可以通过 2 次操作得到。 可以证明少于 2 次操作，无法得到回文串。
提示：
1 <= s.length <= 2000s只包含小写英文字母。s可以通过有限次操作得到一个回文串。
方法一：贪心
由于题目保证原串一定可以变成回文串，那么原串中最多只有一种字母出现奇数次。如果有一种字母出现奇数次，那么将该字母中排在最中间的字符移动到字符串中间，剩下的字符可以转化为所有字母均出现偶数次的情况。
贪心算法是：每次固定字符串最左边的字母
由于数据范围较小，通过
证明：
构造回文串的过程，实际上是每次选择一对字母并把它们交换到字符串头尾的过程。考虑字母
- 字母
$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)$ 次交换。先换哪个都一样。
上述讨论可以得到结论：每次交换最外边出现的字母不劣。因此贪心解法成立。
class Solution:
def minMovesToMakePalindrome(self, s: str) -> int:
cs = list(s)
ans, n = 0, len(s)
i, j = 0, n - 1
while i < j:
even = False
for k in range(j, i, -1):
if cs[i] == cs[k]:
even = True
while k < j:
cs[k], cs[k + 1] = cs[k + 1], cs[k]
k += 1
ans += 1
j -= 1
break
if not even:
ans += n // 2 - i
i += 1
return ansclass Solution {
public int minMovesToMakePalindrome(String s) {
int n = s.length();
int ans = 0;
char[] cs = s.toCharArray();
for (int i = 0, j = n - 1; i < j; ++i) {
boolean even = false;
for (int k = j; k != i; --k) {
if (cs[i] == cs[k]) {
even = true;
for (; k < j; ++k) {
char t = cs[k];
cs[k] = cs[k + 1];
cs[k + 1] = t;
++ans;
}
--j;
break;
}
}
if (!even) {
ans += n / 2 - i;
}
}
return ans;
}
}class Solution {
public:
int minMovesToMakePalindrome(string s) {
int n = s.size();
int ans = 0;
for (int i = 0, j = n - 1; i < j; ++i) {
bool even = false;
for (int k = j; k != i; --k) {
if (s[i] == s[k]) {
even = true;
for (; k < j; ++k) {
swap(s[k], s[k + 1]);
++ans;
}
--j;
break;
}
}
if (!even) ans += n / 2 - i;
}
return ans;
}
};func minMovesToMakePalindrome(s string) int {
cs := []byte(s)
ans, n := 0, len(s)
for i, j := 0, n-1; i < j; i++ {
even := false
for k := j; k != i; k-- {
if cs[i] == cs[k] {
even = true
for ; k < j; k++ {
cs[k], cs[k+1] = cs[k+1], cs[k]
ans++
}
j--
break
}
}
if !even {
ans += n/2 - i
}
}
return ans
}