1328. Break a Palindrome

題目敘述

Given a palindromic string of lowercase English letters palindrome, replace exactly one character with any lowercase English letter so that the resulting string is not a palindrome and that it is the lexicographically smallest one possible.

Return the resulting string. If there is no way to replace a character to make it not a palindrome, return an empty string.

A string a is lexicographically smaller than a string b (of the same length) if in the first position where a and b differ, a has a character strictly smaller than the corresponding character in b. For example, "abcc" is lexicographically smaller than "abcd" because the first position they differ is at the fourth character, and 'c' is smaller than 'd'.

Example 1:

Input: palindrome = "abccba"
Output: "aaccba"
Explanation: There are many ways to make "abccba" not a palindrome, such as "zbccba", "aaccba", and "abacba".
Of all the ways, "aaccba" is the lexicographically smallest.

Example 2:

Input: palindrome = "a"
Output: ""
Explanation: There is no way to replace a single character to make "a" not a palindrome, so return an empty string.

Example 3:

Input: palindrome = "aa"
Output: "ab"

Example 4:

Input: palindrome = "aba"
Output: "abb"

Constraints:

• 1 <= palindrome.length <= 1000
• palindrome consists of only lowercase English letters.

Hint 1:

How to detect if there is impossible to perform the replacement? Only when the length = 1.

Hint 2:

Change the first non 'a' character to 'a'.

Hint 3:

What if the string has only 'a'?

Hint 4:

Change the last character to 'b'.

題目翻譯

如同標題所說的，這題會給一個字串 palindrome，其中的字串都會是回文的。這題就是找出替換一個字串的方式回傳不再是回文的字串。而且要盡量找出權重最小的方式。如同範例中的，參數是 "aba"，不能換成 "abc" 或是 "abd"，因為更低的權重是 "abb"。

解法解析

這題雖然是 Medium，但是解題的邏輯意外的簡單？！因為是回文參數，所以只要替換一個字串就可以打破回文的形式。而為了要讓權重最小，所以直接替換最後一個字元就可以了。其中這個字元只需要考慮是不是 a 即可。因為 a 是權重最小的，所以最後一個字元不是 a 的情況下，將其替換成 a 就可以了。但如果是 a 的話就需要將其換成次小的 b。

這題的解法只需要一個迴圈就能處理，所以 Time complexity 只需要 O(n)，因為只需要儲存一個變數所以 Space complexity 是 O(1)

程式範例

Python

class Solution:
    def breakPalindrome(self, palindrome: str) -> str:
        n = len(palindrome)
        if n == 1:
            return ""
        for i in range(n//2):
            if palindrome[i] != 'a':
                return palindrome[:i]+"a"+palindrome[i+1:]

        return palindrome[:-1]+"b"

JavaScript

/**
 * @param {string} palindrome
 * @return {string}
 */
var breakPalindrome = function (palindrome) {
    const n = palindrome.length;
    if (n === 1) return '';

    for (let i = 0; i < Math.floor(n / 2); i++) {
        if (palindrome[i] !== 'a') {
            return (
                palindrome.substring(0, i) + 'a' + palindrome.substring(i + 1)
            );
        }
    }
    return palindrome.substring(0, n - 1) + 'b';
};

Go

func breakPalindrome(palindrome string) string {
    s := []rune(palindrome)
    if len(s) == 1 {
        return ""
    }
    for i := 0; i < len(s)/2; i++ {
        if s[i] != 'a' {
            s[i] = 'a'
            return string(s)
        }
    }
    s[len(s)-1] = 'b'
    return string(s)
}

Swift

class Solution {
    func breakPalindrome(_ palindrome: String) -> String {
        if palindrome.count == 1 { return "" }
        var arr = Array(palindrome)
        for i in 0..<palindrome.count / 2 {
            if arr[i] == "a"{ continue }
            arr[i] = "a"
            return String(arr)
        }
        arr[arr.count-1] = "b"
        return String(arr)
    }
}

Kotlin

class Solution {
    fun breakPalindrome(palindrome: String): String {
        val n = palindrome.length
        if (n == 1) return ""

        for (i in 0 until (n / 2)) {
            if (palindrome[i] != 'a') {
                return palindrome.replaceFirst(palindrome[i], 'a')
            }
        }

        return palindrome.substring(0, n - 1) + "b"
    }
}