# [1328\. Break a Palindrome](https://leetcode.com/problems/break-a-palindrome/)

- 將迴文改成不是迴文。
- 考慮只有一個字母的情況：`a`、`b`、`c`。
- 走訪字串的一半，遇到不是 `a` 的字母改成 `a`，這樣就不是 palindrome 了。
- 考慮連續 `a` 的情況，例如`aaa`。

:::spoiler Solution

class Solution {
public:
    string breakPalindrome(string palindrome)
    {
        int n = palindrome.size();
        if (n == 1)
        {
            return "";
        }

        for (int i = 0; i < n / 2; ++i)
        {
            if (palindrome[i] != 'a')
            {
                palindrome[i] = 'a';
                return palindrome;
            }
        }
        palindrome.back() = 'b';
        return palindrome;
    }
};

- 時間複雜度：$O(n)$
- 空間複雜度：$O(n)$
:::