# LeetCode Solution, Medium, 1328. Break a Palindrome

# [1328. Break a Palindrome](https://leetcode.com/problems/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

```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

```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

```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

```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

```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"
    }
}
```