1328. Break a Palindrome
Description
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.
Solutions
Solution 1: Greedy
First, we check if the length of the string is $1$. If it is, we directly return an empty string.
Otherwise, we traverse the first half of the string from left to right, find the first character that is not 'a'
, and change it to 'a'
. If no such character exists, we change the last character to 'b'
.
The time complexity is $O(n)$, and the space complexity is $O(n)$. Here, $n$ is the length of the string.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
|