class Solution {
public:
int minMovesToMakePalindrome(string s) {
}
};
2193. 得到回文串的最少操作次数
给你一个只包含小写英文字母的字符串 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 可以通过有限次操作得到一个回文串。原站题解
golang 解法, 执行用时: 8 ms, 内存消耗: 2.1 MB, 提交时间: 2023-09-24 23:34:59
func minMovesToMakePalindrome(s string) int {
n := len(s)
sBytes := []byte(s)
l := 0
r := n - 1
var res int
for l < r {
ptrR := r
for sBytes[l] != sBytes[ptrR] && l < ptrR {
ptrR--
}
if l < ptrR {
for i := ptrR; i < r; i++ {
sBytes[i], sBytes[i+1] = sBytes[i+1], sBytes[i]
res++
}
r--
} else {
res += n/2 - l
}
l++
}
return res
}
python3 解法, 执行用时: 60 ms, 内存消耗: 15.9 MB, 提交时间: 2023-09-24 23:34:24
class Solution:
def minMovesToMakePalindrome(self, s: str) -> int:
ans, n = 0, len(s)
for i in range(n >> 1):
j = s.rindex(s[i])
if j == i:
ans += (n >> 1) - i
s = s[ : i] + s[i + 1:]
n -= 1
j = s.rindex(s[i])
ans += n - 1 - i - j
s = s[ : j ] + s[ j + 1: n - i ]
return ans
java 解法, 执行用时: 14 ms, 内存消耗: 42.9 MB, 提交时间: 2023-09-24 23:33:36
class Solution {
public int minMovesToMakePalindrome(String s) {
// System.out.println(s);
if (s.length() <= 1) return 0;
char c = s.charAt(0);
for (int j = s.length() - 1; j > 0; j--) {
if (s.charAt(j) == c) {
return s.length() - 1 - j + minMovesToMakePalindrome(s.substring(1, j) + s.substring(j + 1));
}
}
int mid = (s.length() / 2);
return mid + minMovesToMakePalindrome(s.substring(1, mid + 1) + s.substring(mid + 1));
}
}
cpp 解法, 执行用时: 20 ms, 内存消耗: 7 MB, 提交时间: 2023-09-24 23:32:23
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;
}
};