字典序最小回文串

难度: Easy

给你一个由 小写英文字母 组成的字符串 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 仅由小写英文字母组成

Submission

运行时间: 65 ms

内存: 16.2 MB

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

Explain

解题思路是通过两个指针从字符串的两端向中间遍历，比较对应的字符。如果两个字符不同，则选择两者中较小的字符来替换较大的字符，以此来确保最终结果的字典序尽可能小。这样操作直到两个指针相遇或者交错，最后的字符串就是字典序最小的回文串。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def makeSmallestPalindrome(self, s: str) -> str:
        l = list(s)  # 将字符串转换成字符列表以便修改
        for i in range(len(l)//2):  # 只需遍历到字符串的一半
            x = l[i]  # 左侧字符
            y = l[-1-i]  # 右侧对应的字符
            if x > y:
                l[i] = y  # 如果左侧字符较大，则替换为较小的右侧字符
            else:
                l[-1-i] = x  # 如果右侧字符较大，则替换为较小的左侧字符
        return ''.join(l)  # 将列表转换回字符串并返回

Explore

在构造字典序最小的回文串时，选择较小的字符替换较大的字符是为了确保所形成的回文串尽可能小。字典序是按字符从左到右比较的，较小的字符会使得整个字符串的字典序更小。通过这种方法，可以在保证字符串是回文的同时，也确保了其在所有可能的回文串中字典序最小。

如果在遍历过程中两个指针指向的字符相同，实际上不需要进行任何操作，因为这两个字符已经满足了回文串的对称性要求。算法只需继续移动指针，检查下一对字符。

无论字符串长度是奇数还是偶数，遍历到字符串的一半即可完成回文的构造，因为回文串是关于中心对称的。对于偶数长度的字符串，每个字符都有对应的对称字符；对于奇数长度的字符串，中间的字符不需要对称，它自己即是中心点。因此，算法只需关注对称的字符是否一致或调整到一致即可。

本算法确实考虑了这些边界情况。如果字符串中所有字符相同，则每次比较的字符都是相同的，算法不会进行任何替换操作，直接返回原字符串即可。如果字符串已经是一个回文串，同样由于每次比较的字符相同或正确对称，不需要替换，算法也会直接返回原字符串。这些情况下算法的表现是正确且高效的。