[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.

破坏回文串。

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

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

如果两个字符串长度相同，那么字符串 a 字典序比字符串 b 小可以这样定义：在 a 和 b 出现不同的第一个位置上，字符串 a 中的字符严格小于 b 中的对应字符。例如，”abcc” 字典序比 “abcd” 小，因为不同的第一个位置是在第四个字符，显然 ‘c’ 比 ‘d’ 小。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/break-a-palindrome
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

题目的 input 给的是一个合法的回文串，我们要做的是修改其中的一个字母，从而使得修改过后的字符串不是回文串同时字典序最小。

我们回顾回文串的定义，发现回文串只有两种情况，一种是 abba，一种是 aba。同时既然需要做到修改之后字典序最小，那么我们只看字符串的左半边就好了，看右半边是无法做到修改后的结果是字典序最小的。这道题我们需要注意两个 corner case，一个是如果 input 中字母都是a，类似 aaaaaaa 的话，那么我们只能通过把最后一个 a 改成 b 来保证修改结果字典序最小。另外一个 case 是比如例子二，如果不能通过修改字母来破坏 input 字符串的回文，那么我们只能将他改成空字符串返回。

复杂度

时间O(n)
空间O(n) - char array

代码

Java实现

class Solution {
    public String breakPalindrome(String palindrome) {
        int n = palindrome.length();
        char[] letters = palindrome.toCharArray();
        int left = 0;
        int right = n - 1;
        while (left < right) {
            char c = letters[left];
            if (c != 'a') {
                letters[left] = 'a';
                return new String(letters);
            }
            left++;
            right--;
        }

        letters[n - 1] = 'b';
        if (n <= 1) {
            return "";
        }
        return new String(letters);
    }
}