How do I solve the Lexicographically Smallest Palindrome problem?

Use two-pointer scanning to compare characters at both ends of the string. Modify the larger character to the smaller one, ensuring minimal changes.

What is the time complexity of the Lexicographically Smallest Palindrome problem?

The time complexity is O(n), where n is the length of the string, as you only scan the string once with two pointers.

How do I prioritize the lexicographically smallest palindrome?

Whenever characters mismatch, replace the larger character with the smaller one to make the result lexicographically smallest.

What if the string is already a palindrome?

If the string is already a palindrome, no changes are needed, and the output will be the same as the input string.

Can I solve this problem without using the two-pointer technique?

While other techniques are possible, the two-pointer technique is the most efficient and optimal for this problem, ensuring minimal operations.

#2697

Easy

auto_awesome双·指针·invariant

LeetCode 题解工作台

字典序最小回文串

给你一个由小写英文字母组成的字符串 s ，你可以对其执行一些操作。在一步操作中，你可以用其他小写英文字母替换 s 中的一个字符。请你执行尽可能少的操作，使 s 变成一个回文串。如果执行最少操作次数的方案不止一种，则只需选取字典序最小的方案。对于两个长度相同的字符串 a 和 …

双指针字符串贪心

题目描述

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

lightbulb

解题思路

方法一：贪心 + 双指针

我们用两个指针 $i$ 和 $j$ 分别指向字符串的首尾，初始时 $i = 0$ , $j = n - 1$ 。

接下来，我们每一次都贪心地将 $s[i]$ 和 $s[j]$ 修改为它们中的较小值，使得它们相等。然后将 $i$ 向后移动一位，将 $j$ 向前移动一位，继续进行这一过程，直到 $i \ge j$ 为止。此时，我们就得到了最小的回文串。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 是字符串的长度。

1

2

3

4

5

6

7

8

9

class Solution:
    def makeSmallestPalindrome(self, s: str) -> str:
        cs = list(s)
        i, j = 0, len(s) - 1
        while i < j:
            cs[i] = cs[j] = min(cs[i], cs[j])
            i, j = i + 1, j - 1
        return "".join(cs)

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Tests understanding of two-pointer techniques and string manipulation.
question_mark
Checks for the ability to implement a greedy strategy to minimize changes.
question_mark
Evaluates efficiency in handling strings of up to 1000 characters.

warning

常见陷阱

外企场景

error
Over-complicating the approach by introducing unnecessary operations.
error
Failing to prioritize lexicographically smallest changes when characters mismatch.
error
Not optimizing the solution for time and space complexity, especially for larger input strings.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Consider an approach where the string is already a palindrome.
arrow_right_alt
Test cases where multiple palindromes are possible with the same number of changes.
arrow_right_alt
Explore the case where no changes are needed, testing the efficiency of the solution.

help

常见问题

外企场景

继续练习

#2486 追加字符以获得子序列 #2472 不重叠回文子字符串的最大数目 #2938 区分黑球与白球