题目描述

给你一个回文字符串 palindrome，请你将其中 一个 字符用任意小写英文字母替换，使得结果字符串的字典序最小，且 不是 回文串。

请你返回结果字符串。如果无法做到，则返回一个空串。

样例

输入：palindrome = "abccba"
输出："aaccba"

输入：palindrome = "a"
输出：""

限制

• 1 <= palindrome.length <= 1000
• palindrome 只包含小写英文字母。

算法

(贪心) $O(n)$

1. 如果字符串长度为 1，则直接返回空串。
2. 接下来尝试将第一个不是 a 的字符变成 a。如果字符串长度为奇数，则不允许将正中间的字符变为 a。
3. 如果找不到一个可以变的字符位置，则将最末尾的字符变为 b。

时间复杂度

• 仅遍历字符串一次，故时间复杂度为 $O(n)$。

空间复杂度

• 仅需要常数的额外空间。

C++ 代码

class Solution {
public:
    string breakPalindrome(string palindrome) {
        size_t n = palindrome.length();
        if (n == 1)
            return "";

        for (int i = 0; i < n; i++) {
            if ((n & 1) && i == n / 2)
                continue;

            if (palindrome[i] != 'a') {
                palindrome[i] = 'a';
                return palindrome;
            }
        }

        palindrome.back() = 'b';
        return palindrome;
    }
};