Leetcode: Break a Palindrome

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)
}