Skip to content

Prepare For Coder Interview – Denny

  • Basic
  • Medium
  • Hard
  • Architect
  • Life

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)
}
linkedin
github
slack

Post Views: 0
Posted in MediumTagged #greedy, #palindrome, #string

Post navigation

LeetCode: Rank Transform of an Array
LeetCode: Sort the Matrix Diagonally

Leave a Reply Cancel reply

Your email address will not be published.

Tags

#array #backtracking #bfs #binarytree #bitmanipulation #blog #classic #codetemplate #combination #dfs #dynamicprogramming #game #graph #greedy #heap #inspiring #interval #linkedlist #manydetails #math #palindrome #recursive #slidingwindow #stack #string #subarray #trie #twopointer #twosum binarysearch editdistance hashmap intervaldp knapsack monotone oodesign presum rectangle redo review rotatelist series sql treetraversal unionfind

Recent Posts

  • a
  • a
  • a
  • a
  • a

Recent Comments

    Archives

    Categories

    • Amusing
    • Basic
    • Easy
    • Hard
    • Life
    • Medium
    • Resource
    • Review
    • Series
    • Uncategorized
    Proudly powered by WordPress | Theme: petals by Aurorum.