LeetCode: Break a Palindrome Posted on August 5, 2019July 26, 2020 by braindenny Break a Palindrome Similar Problems: CheatSheet: LeetCode For Code Interview CheatSheet: Common Code Problems & Follow-ups Tag: #palindrome, #string, #greedy 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. Github: code.dennyzhang.com Credits To: leetcode.com Leave me comments, if you have better ways to solve. Solution: // https://code.dennyzhang.com/break-a-palindrome // Basic Ideas: greedy // // Complexity: Time O(K), Space O(1) // K = len(str) func breakPalindrome(palindrome string) string { if len(palindrome) == 1 { return "" } bytes := []byte(palindrome) // Note: shouldn't change the middle, since it will still be a palindrome // left: change to 'a' for i:=0; i<len(bytes)/2; i++ { if bytes[i] != 'a' { bytes[i] = 'a' return string(bytes) } } // all aaXaa bytes[len(bytes)-1] = 'b' return string(bytes) } Post Views: 0