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

难度: Hard

给你一个只包含小写英文字母的字符串 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 <= 2000
s 只包含小写英文字母。
s 可以通过有限次操作得到一个回文串。

Submission

运行时间: 40 ms

内存: 16.2 MB

class Solution:
    def minMovesToMakePalindrome(self, s: str) -> int:
        # 递归
        n = len(s)
        if n <= 2:
            return 0
        cnt = idx = 0
        idx = s.rfind(s[0])  # 找到最靠近s末位的s[0]的下标
        if idx == 0:
            cnt = n // 2  # s[0]的个数只有1个，s长度原本是奇数
        else:
            cnt = n - 1 - idx  # 计算从idx移动到末尾的距离
        return cnt + self.minMovesToMakePalindrome(s[1:idx] + s[idx + 1:])

    # def minMovesToMakePalindrome(self, s: str) -> int:
    #     # 移动元素耗费时间
    #     s = list(s)
    #     res, n = 0, len(s)
    #     l, r = 0, n - 1
    #     while l < r:
    #         k = r
    #         while k > l and s[k] != s[l]:
    #             k -= 1
    #         if k == l:  # 当前元素个数为奇数
    #             res += (r - l) // 2
    #         else:
    #             res += r - k
    #             while k < r:  # 元素右移
    #                 s[k], s[k + 1] = s[k + 1], s[k]
    #                 k += 1
    #             r -= 1
    #         l += 1
    #     return res

    def minMovesToMakePalindrome(self, s: str) -> int:
        res = 0
        while len(s) > 2:
            l = r = len(s) - 1
            # while s[l] != s[0]:
            #     l -= 1
            l = s.rfind(s[0])  # 查找效率高
            if l == 0:  # 当前元素个数为奇数
                res += r // 2
                s = s[1:]
            else:
                res += r - l
                s = s[1:l] + s[l + 1:]
        return res

Explain

这个题解实现了一个递归的方法来将字符串转换为回文串。首先，检查字符串的第一个字符在字符串中最后一次出现的位置。如果这个字符只出现一次（即在字符串的开始位置），则这个字符是回文中心，需要移动到字符串的中心位置，这将消耗 n/2 次操作（n 是字符串的长度）。否则，如果字符在末尾之前的位置出现，将这个字符通过交换移动到末尾，然后递归地在剩余的子字符串（移除了当前处理的两个字符）上应用同样的过程。继续这个过程直到字符串长度小于或等于2，这时不需要更多的操作。通过逐步将匹配的字符移动到开头和结尾，逐渐构建出回文字符串。

时间复杂度: O(n^2)

空间复杂度: O(n^2)

# Python 代码带注释

class Solution:
    def minMovesToMakePalindrome(self, s: str) -> int:
        res = 0
        while len(s) > 2:
            r = len(s) - 1  # 初始将r设为字符串末端
            l = s.rfind(s[0])  # 查找字符串中第一个字符最后一次出现的位置
            if l == 0:  # 如果该字符只出现一次
                res += r // 2  # 该字符需要移动到字符串中心，消耗 r//2 次操作
                s = s[1:]  # 移除该字符后递归处理剩余字符串
            else:
                res += r - l  # 将该字符移动到字符串末尾的操作次数
                s = s[1:l] + s[l + 1:]  # 移除两端已处理的字符后，继续处理中间部分
        return res

Explore

当第一个字符在字符串中只出现一次，说明它无法与其他字符形成对称的配对，因此它必须成为回文串的中心。回文串的特性是中心对称，所以单个出现的字符适合放在中心位置，以确保左右对称性不被破坏。此外，从效率角度考虑，将其移动到中心也是操作次数最少的方案，因为从任意位置到中心的距离通常小于到端点的距离。

从字符串的第一个字符开始处理，可以简化问题的复杂性。这种方法允许我们逐步减小问题的规模，通过每次处理两个对称位置的字符，逐渐向字符串中心推进。从第一个字符开始也有助于在每一步中清楚地定义和解决问题，而从中间或其他位置开始可能会增加处理字符顺序和确定哪些字符需要移动的复杂性。

在递归处理中，每一步都是基于确保最终字符串成为回文串的目标来设计的。尽管移除两端已处理的字符后的新字符串在当前状态下可能不是回文串，但递归方法确保了通过继续处理可以将其转变为回文串。每一步移除的字符都是对称的，因此理论上剩余的字符串应该是能够通过进一步的操作转换成回文串的。

当字符串长度为奇数时，中心位置将有一个字符，这个字符是唯一的并且不需要与其他字符配对。在实现中，当遇到这样的字符时，我们通常会检测它是否只出现一次且位于字符串的中心位置。如果是这样，我们不需要对它执行任何操作。如果不是，我们会将其通过最少的操作移动到中心位置。这是确保字符串成为回文的必要步骤，因为中心位置的字符不需要与任何字符配对。