Given a palindromic string palindrome
, replace exactly one character by any lowercase English letter so that the string becomes the lexicographically smallest possible string that isn’t a palindrome.
After doing so, return the final string. If there is no way to do so, return the empty string.
Example 1:
Input: palindrome = "abccba" Output: "aaccba"
Example 2:
Input: palindrome = "a" Output: ""
Constraints:
1 <= palindrome.length <= 1000
palindrome
consists of only lowercase English letters.
Solution: Greedy
For the first half of the string, replace the first non ‘a’ character to ‘a’.
e.g. abcdcba => aacdcba
If not found which means the the entire string is ‘a’ expect the middle one if the length is odd, like aa or aba, replace the last character to ‘b’.
aa => ab
aba => abb
Time complexity: O(n)
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
// Author: Huahua class Solution { public: string breakPalindrome(string palindrome) { const int n = palindrome.length(); if (n == 1) return ""; for (int i = 0; i < n / 2; ++i) { if (palindrome[i] != 'a') { palindrome[i] = 'a'; return palindrome; } } palindrome.back() = 'b'; return palindrome; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment