# 1328. Break a Palindrome

• Time: $O(n)$
• Space: $O(n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 class Solution { public: string breakPalindrome(string palindrome) { if (palindrome.length() == 1) return ""; for (int i = 0; i < palindrome.length() / 2; ++i) if (palindrome[i] != 'a') { palindrome[i] = 'a'; return palindrome; } palindrome.back() = 'b'; return palindrome; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 class Solution { public String breakPalindrome(String palindrome) { if (palindrome.length() == 1) return ""; StringBuilder sb = new StringBuilder(palindrome); for (int i = 0; i < palindrome.length() / 2; ++i) if (palindrome.charAt(i) != 'a') { sb.setCharAt(i, 'a'); return sb.toString(); } sb.setCharAt(sb.length() - 1, 'b'); return sb.toString(); } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 class Solution: def breakPalindrome(self, palindrome: str) -> str: if len(palindrome) == 1: return '' ans = list(palindrome) for i in range(len(palindrome) // 2): if palindrome[i] != 'a': ans[i] = 'a' return ''.join(ans) ans[-1] = 'b' return ''.join(ans)