Skip to content

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)