Easy

题目描述

给你一个由小写英文字母组成的字符串 s，你可以对其执行一些操作。在一次操作中，你可以用另一个小写英文字母替换 s 中的一个字符。

你的任务是使 s 成为一个回文串，所需的操作次数最少。如果有多个回文串都可以通过最少次数的操作得到，则要使字典序最小的那个。

如果在字符串 a 和 b（长度相同）不同的第一个位置上，a 中的字母在字母表中出现的位置比 b 中对应字母的位置要早，那么字符串 a 在字典序上比字符串 b 小。

返回结果回文串。

示例 1：

输入：s = "egcfe"
输出："efcfe"
解释：将 "egcfe" 变成回文串的最少操作次数为 1，通过修改一个字符得到字典序最小的回文串是 "efcfe"，修改 'g'。

示例 2：

输入：s = "abcd"
输出："abba"
解释：将 "abcd" 变成回文串的最少操作次数为 2，通过修改两个字符得到字典序最小的回文串是 "abba"。

示例 3：

输入：s = "seven"
输出："neven"
解释：将 "seven" 变成回文串的最少操作次数为 1，通过修改一个字符得到字典序最小的回文串是 "neven"。

提示：

  • 1 <= s.length <= 1000
  • s 仅由小写英文字母组成

解题思路

这道题要求我们用最少的操作次数将字符串变成回文串，并且在多个最优解中选择字典序最小的。

核心思路：

  1. 双指针遍历：使用两个指针分别从字符串的开头和结尾向中间移动，比较对称位置的字符
  2. 贪心策略：当两个对称位置的字符不同时，我们需要将其中一个修改为另一个。为了保证字典序最小，应该将两个字符都改为较小的那个字符
  3. 最小操作次数：每对不匹配的对称字符只需要一次操作（修改其中一个），这样就能保证操作次数最少

算法步骤：

  1. 将字符串转换为字符数组便于修改
  2. 使用双指针 left 和 right 分别从字符串两端开始
  3. 当 s[left] != s[right] 时，将两个位置都设置为 min(s[left], s[right])
  4. 移动指针直到相遇

这种方法既保证了最少的操作次数，又确保了结果的字典序最小。时间复杂度为 O(n)，空间复杂度为 O(n)（用于存储结果）。

代码实现

class Solution {
public:
    string makeSmallestPalindrome(string s) {
        int n = s.length();
        int left = 0, right = n - 1;
        
        while (left < right) {
            if (s[left] != s[right]) {
                char smaller = min(s[left], s[right]);
                s[left] = smaller;
                s[right] = smaller;
            }
            left++;
            right--;
        }
        
        return s;
    }
};

class Solution:
    def makeSmallestPalindrome(self, s: str) -> str:
        s = list(s)
        left, right = 0, len(s) - 1
        
        while left < right:
            if s[left] != s[right]:
                smaller = min(s[left], s[right])
                s[left] = smaller
                s[right] = smaller
            left += 1
            right -= 1
        
        return ''.join(s)

public class Solution {
    public string MakeSmallestPalindrome(string s) {
        char[] chars = s.ToCharArray();
        int left = 0, right = chars.Length - 1;
        
        while (left < right) {
            if (chars[left] != chars[right]) {
                char smaller = (char)Math.Min(chars[left], chars[right]);
                chars[left] = smaller;
                chars[right] = smaller;
            }
            left++;
            right--;
        }
        
        return new string(chars);
    }
}

var makeSmallestPalindrome = function(s) {
    let chars = s.split('');
    let left = 0, right = chars.length - 1;
    
    while (left < right) {
        if (chars[left] !== chars[right]) {
            let smaller = chars[left] < chars[right] ? chars[left] : chars[right];
            chars[left] = smaller;
            chars[right] = smaller;
        }
        left++;
        right--;
    }
    
    return chars.join('');
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n)需要遍历字符串的一半，其中 n 是字符串长度
空间复杂度O(n)需要额外空间存储字符数组或修改后的字符串