[LeetCode] 1328. Break a Palindrome 破坏回文串

Given a palindromic string of lowercase English letters palindrome, replace exactly one character with any lowercase English letter so that the resulting string is not a palindrome and that it is the lexicographically smallest one possible.

Return the resulting string. If there is no way to replace a character to make it not a palindrome, return an empty string.

A string a is lexicographically smaller than a string b (of the same length) if in the first position where a and b differ, a has a character strictly smaller than the corresponding character in b. For example, "abcc" is lexicographically smaller than "abcd" because the first position they differ is at the fourth character, and 'c' is smaller than 'd'.

Example 1:

Input: palindrome = "abccba"
Output: "aaccba"
Explanation: There are many ways to make "abccba" not a palindrome, such as "zbccba", "aaccba", and "abacba".
Of all the ways, "aaccba" is the lexicographically smallest.

Example 2:

Input: palindrome = "a"
Output: ""
Explanation: There is no way to replace a single character to make "a" not a palindrome, so return an empty string.

Constraints:

1 <= palindrome.length <= 1000
palindrome consists of only lowercase English letters.

这道题给了一个只有小写字母的回文串，现在让我们改动一个字母，使其变为非回文串，且字母顺序最小。对于回文串，想必大家都不陌生，就是从首尾两端往中间看，对应两端的字母都依次相等，除了奇数个字母中的最中间第一个例外，比如 aabaa 中间的b。题目中还说了，若无法使其变为非回文串，则返回空串。那么就来想一下，什么情况下无法变为非回文串，其实就是当只有一个字母时，根据回文串的定义，单个字母也算回文串，所以无论将该字母换成任何其他字母时，其仍然是回文串。这里可以在开头判断一下，若给定的回文串长度为1，则直接返回空串。

若长度超过1的话，就要考虑一下具体的置换策略了，根据例子1的字符串 "abccba" 来分析，第一个字母是a，不可能再变的更小，而第二个字母是b，可以通过变成a，来变为非回文串，且字母顺序最小，于是策略就是从前往后遍历，遇到第一个非a的字母，改变为a就行了，由于回文串的对称性，只需要遍历前半个字符串就行了。但其实题目中漏掉了一种情况，比如 "aabaa" 或者 "aaaa"，这两个字符串的前半部分都是a，而将前半段中的任何的a变为b，虽然变为了非回文串，但却不是字母顺序最小了，正确的方法应该是将整个回文串的最后一个a变为b，这样才能得到字母顺序最小的非回文串，参见代码如下：

class Solution {
public:
    string breakPalindrome(string palindrome) {
        int n = palindrome.size(), half = n / 2;
        if (n == 1) return "";
        for (int i = 0; i < half; ++i) {
            if (palindrome[i] != 'a') {
                palindrome[i] = 'a';
                return palindrome;
            }
        }
        palindrome[n - 1] = 'b';
        return palindrome;
    }
};

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1328

参考资料：

https://leetcode.com/problems/break-a-palindrome/

https://leetcode.com/problems/break-a-palindrome/solutions/489774/java-c-python-easy-and-concise/

LeetCode All in One 题目讲解汇总(持续更新中...)