题目描述
给你一个由 小写英文字母 组成的字符串 s
,你可以对其执行一些操作。在一步操作中,你可以用其他小写英文字母 替换 s
中的一个字符。
请你执行 尽可能少的操作,使 s
变成一个 回文串。如果执行 最少 操作次数的方案不止一种,则只需选取 字典序最小 的方案。
对于两个长度相同的字符串 a
和 b
,在 a
和 b
出现不同的第一个位置,如果该位置上 a
中对应字母比 b
中对应字母在字母表中出现顺序更早,则认为 a
的字典序比 b
的字典序要小。
返回最终的回文字符串。
样例
输入:s = "egcfe"
输出:"efcfe"
解释:将 "egcfe" 变成回文字符串的最小操作次数为 1,
修改 1 次得到的字典序最小回文字符串是 "efcfe",只需将 'g' 改为 'f'。
输入:s = "abcd"
输出:"abba"
解释:将 "abcd" 变成回文字符串的最小操作次数为 2,
修改 2 次得到的字典序最小回文字符串是 "abba"。
输入:s = "seven"
输出:"neven"
解释:将 "seven" 变成回文字符串的最小操作次数为 1,
修改 1 次得到的字典序最小回文字符串是 "neven"。
限制
1 <= s.length <= 1000
s
仅由小写英文字母组成。
算法
(双指针) $O(n)$
- 定义两个指针分别从两侧遍历字符串,如果两个回文位置字符不一样,则无论如何都需要调整一次,且调整后的字符为两个位置上较小的字符。
时间复杂度
- 遍历字符串一次,故时间复杂度为 $O(n)$。
空间复杂度
- 仅需要常数的额外空间。
C++ 代码
class Solution {
public:
string makeSmallestPalindrome(string s) {
const int n = s.size();
for (int i = 0, j = n - 1; i < j; i++, j--) {
if (s[i] > s[j]) s[i] = s[j];
else s[j] = s[i];
}
return s;
}
};