Break a Palindrome

Description

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(javascript)

/** 暴力解法 O(n^2)
 * @param {string} palindrome
 * @return {string}
 */
// const breakPalindrome = function (palindrome) {
//   const isPalindrome = (str) => {
//     let i = 0
//     let j = str.length - 1
//     while (i <= j) {
//       if (str[i] !== str[j]) {
//         return false
//       }
//       i++
//       j--
//     }
//     return true
//   }
//   let result = ''
//   for (let i = 0; i < palindrome.length; i++) {
//     for (let j = 97; j < 97 + 26; j++) {
//       const current = `${palindrome.slice(0, i)}${String.fromCharCode(j)}${palindrome.slice(i + 1)}`
//       if (!isPalindrome(current)) {
//         if (!result) {
//           result = current
//         } else {
//           result = result < current ? result : current
//         }
//       }
//     }
//   }
//   return result
// }


const breakPalindrome = function (palindrome) {
  if (palindrome.length <= 1) {
    return ''
  }
  for (let i = 0; i < Math.floor(palindrome.length / 2); i++) {
    if (palindrome[i] !== 'a') {
      return `${palindrome.slice(0, i)}a${palindrome.slice(i + 1)}`
    }
  }
  return `${palindrome.slice(0, palindrome.length - 1)}b`
}