Hard

题目描述

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

在一次移动中，你可以选择 s 中任意两个相邻的字符并交换它们。

返回使 s 变成回文串所需的最少移动次数。

注意：输入保证 s 总是可以转换为回文串。

示例 1：

输入：s = "aabb"
输出：2
解释：
我们可以从 s 得到两个回文串："abba" 和 "baab"。
- 我们可以用 2 次移动从 s 得到 "abba"："aabb" -> "abab" -> "abba"。
- 我们可以用 2 次移动从 s 得到 "baab"："aabb" -> "abab" -> "baab"。
因此，使 s 变成回文串所需的最少移动次数是 2。

示例 2：

输入：s = "letelt"
输出：2
解释：
我们可以用 2 次移动从 s 得到回文串 "lettel"。
其中一种方法是："letelt" -> "letetl" -> "lettel"。
诸如 "tleelt" 的其他回文串也可以用 2 次移动得到。
可以证明少于 2 次移动无法得到回文串。

约束条件：

  • 1 <= s.length <= 2000
  • s 只包含小写英文字母
  • s 可以在有限次移动内转换为回文串

解题思路

这是一个经典的贪心问题。核心思路是从外向内逐层构造回文串。

基本思路：

  1. 对于当前的左端点字符，我们需要在右半部分找到与它匹配的字符
  2. 将找到的匹配字符通过相邻交换移动到对应的右端点位置
  3. 删除已配对的字符，递归处理内部子串

特殊情况处理：

  • 如果字符串长度为奇数，中间的字符可以单独存在，不需要配对
  • 当某个字符在字符串中只出现一次时，它必须放在中间位置

算法步骤：

  1. 使用递归或迭代的方式，每次处理最外层的字符对
  2. 对于当前左端点字符 s[left]，从右端点开始向左查找相同字符
  3. 找到匹配字符后，通过相邻交换将其移动到 right 位置
  4. 累计交换次数，然后缩小搜索范围继续处理

优化考虑： 可以使用树状数组或其他数据结构来优化查找和移动过程，但对于题目给定的数据规模，简单的贪心算法已经足够高效。

代码实现

class Solution {
public:
    int minMovesToMakePalindrome(string s) {
        int moves = 0;
        int n = s.length();
        
        for (int left = 0; left < n / 2; left++) {
            int right = n - 1 - left;
            
            // 找到与 s[left] 匹配的字符
            int match = right;
            while (match > left && s[match] != s[left]) {
                match--;
            }
            
            // 如果是奇数长度且找到中间位置，将其移到中心
            if (match == left) {
                moves += n / 2 - left;
            } else {
                // 将匹配的字符移动到 right 位置
                while (match < right) {
                    swap(s[match], s[match + 1]);
                    match++;
                    moves++;
                }
            }
        }
        
        return moves;
    }
};

class Solution:
    def minMovesToMakePalindrome(self, s: str) -> int:
        s = list(s)  # 转换为列表便于修改
        moves = 0
        n = len(s)
        
        left = 0
        while left < n // 2:
            right = n - 1 - left
            
            # 找到与 s[left] 匹配的字符
            match = right
            while match > left and s[match] != s[left]:
                match -= 1
            
            # 如果是奇数长度且找到中间位置，将其移到中心
            if match == left:
                moves += n // 2 - left
            else:
                # 将匹配的字符移动到 right 位置
                while match < right:
                    s[match], s[match + 1] = s[match + 1], s[match]
                    match += 1
                    moves += 1
            
            left += 1
        
        return moves

public class Solution {
    public int MinMovesToMakePalindrome(string s) {
        char[] chars = s.ToCharArray();
        int moves = 0;
        int n = chars.Length;
        
        for (int left = 0; left < n / 2; left++) {
            int right = n - 1 - left;
            
            // 找到与 chars[left] 匹配的字符
            int match = right;
            while (match > left && chars[match] != chars[left]) {
                match--;
            }
            
            // 如果是奇数长度且找到中间位置，将其移到中心
            if (match == left) {
                moves += n / 2 - left;
            } else {
                // 将匹配的字符移动到 right 位置
                while (match < right) {
                    (chars[match], chars[match + 1]) = (chars[match + 1], chars[match]);
                    match++;
                    moves++;
                }
            }
        }
        
        return moves;
    }
}

var minMovesToMakePalindrome = function(s) {
    let arr = s.split('');
    let moves = 0;
    let left = 0;
    let right = arr.length - 1;
    
    while (left < right) {
        if (arr[left] === arr[right]) {
            left++;
            right--;
            continue;
        }
        
        let k = right - 1;
        while (k > left && arr[k] !== arr[left]) {
            k--;
        }
        
        if (k === left) {
            [arr[left], arr[left + 1]] = [arr[left + 1], arr[left]];
            moves++;
        } else {
            while (k < right) {
                [arr[k], arr[k + 1]] = [arr[k + 1], arr[k]];
                k++;
                moves++;
            }
            left++;
            right--;
        }
    }
    
    return moves;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度分析
时间复杂度O(n²)
空间复杂度O(1) 或 O(n)

说明：

  • 时间复杂度：外层循环 O(n/2)，内层查找和移动最坏情况下都是 O(n)，总体为 O(n²)
  • 空间复杂度：C++ 版本为 O(1)（原地修改），Python/JavaScript 版本为 O(n)（需要额外数组存储）

相关题目