2697-字典序最小回文串

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

请你执行 尽可能少的操作 ，使 s 变成一个 回文串 。如果执行 最少 操作次数的方案不止一种，则只需选取 字典序最小
的方案。

对于两个长度相同的字符串 a 和 b ，在 a 和 b 出现不同的第一个位置，如果该位置上 a 中对应字母比 b
中对应字母在字母表中出现顺序更早，则认为 a 的字典序比 b 的字典序要小。

返回最终的回文字符串。

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

本题视频讲解

见【周赛 346】 第二题，欢迎点赞投币！

思路

对于两个中心对称的字母 x=s[i] 和 y=s[n-1-i]，如果 x\ne y，那么只需要修改一次，就可以让这两个字母相同：把 x 改成 y 或者把 y 改成 x。

• 如果 x>y，那么把 x 修改成 y 更好，这样字典序更小。
• 如果 x<y，那么把 y 修改成 x 更好，这样字典序更小。

代码实现时可以把 x=y 的情况合并到 x<y 中，从而少写一个 else if 的判断逻辑。

[sol-Python3]

class Solution:
    def makeSmallestPalindrome(self, s: str) -> str:
        s = list(s)
        for i in range(len(s) // 2):
            x, y = s[i], s[-1 - i]
            if x > y: s[i] = y
            else: s[-1 - i] = x
        return ''.join(s)

[sol-Java]

class Solution {
    public String makeSmallestPalindrome(String S) {
        var s = S.toCharArray();
        for (int i = 0, n = s.length; i < n / 2; i++) {
            char x = s[i], y = s[n - 1 - i];
            if (x > y) s[i] = y;
            else s[n - 1 - i] = x;
        }
        return new String(s);
    }
}

[sol-C++]

class Solution {
public:
    string makeSmallestPalindrome(string s) {
        for (int i = 0, n = s.length(); i < n / 2; i++) {
            char x = s[i], y = s[n - 1 - i];
            if (x > y) s[i] = y;
            else s[n - 1 - i] = x;
        }
        return s;
    }
};

[sol-Go]

func makeSmallestPalindrome(S string) string {
	s := []byte(S)
	for i, n := 0, len(s); i < n/2; i++ {
		x, y := s[i], s[n-1-i]
		if x > y {
			s[i] = y
		} else {
			s[n-1-i] = x
		}
	}
	return string(s)
}

复杂度分析

• 时间复杂度：\mathcal{O}(n)，其中 n 为 s 的长度。
• 空间复杂度：\mathcal{O}(n) 或 \mathcal{O}(1)。取决于能否直接修改 s。