2697. 字典序最小回文串

🎯 问题描述（来源于LeetCode）

描述：
给定一个由小写英文字母组成的字符串 s，你每次操作可以将任意一个字符修改为任意一个小写字母。
请你返回将 s 变成回文串所需的最少操作次数？不，本题要求构造一个字典序最小的回文串，即通过修改某些字符（不限制操作次数），使得最终字符串是回文串，且字典序最小。

说明：

  • 字典序比较：按从左到右的顺序比较字符。
  • 回文串：正读反读相同。
  • 可以修改任意位置的字符为任意小写字母。

示例：

  • 示例 1：
1
2
3
输入: s = "egcfe"
输出: "efcfe"
解释: 将 'g' 改为 'f'，得到 "efcfe" 是回文串，且字典序最小。
  • 示例 2：
1
2
3
输入: s = "abcd"
输出: "abba"
解释: 将 'c' 改为 'b'，'d' 改为 'a'，得到 "abba" 是回文串，且字典序最小。

💻 解题思路

思路：双指针 + 贪心修改

算法步骤

  1. 将字符串转为列表 st，便于原地修改。
  2. 设置左指针 left = 0，右指针 right = len(s) - 1。
  3. 当 left < right 时：
    • 如果 st[left] != st[right]，则取两者中较小的字符 ch = min(st[left], st[right])，将两端都改为 ch（因为字典序要最小，应尽可能让左边的字符小）。
    • 移动指针：left += 1，right -= 1。
  4. 返回列表转字符串。

代码实现（您的代码）

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def makeSmallestPalindrome(self, s: str) -> str:
        left, right = 0, len(s) - 1
        st = list(s)
        while left < right:
            while st[left] != st[right]:
                ch = min(st[left], st[right])
                st[left] = ch
                st[right] = ch
            left += 1
            right -= 1
        return "".join(st)

📊 性能分析

  • 时间复杂度：O(n)O(n)，每个字符访问一次。
  • 空间复杂度：O(n)O(n)，列表存储字符串（可原地修改）。

思考

您的代码使用内层 while 循环来确保两端字符相等，实际上由于每次只会修改一次，内层循环最多执行一次，可以简化为 if 判断。但当前写法逻辑正确且能通过。
关键点：将两端都改为较小的字符，使得字典序最小。例如 'e' 和 'g' 改为 'e'，因为左边字符越小字典序越小。
该解法是本题的标准贪心策略，简洁高效。