[Java] Break palindrome

Given a palindrome string, change any character in order to form the lexicographically earliest non palindrome.

Example:

"a" return ""

"aa" return "ab"

"aba" return "abb"

We have two options: change an initial 'a' character in the first half (excluding middle point) or change a last 'a' or 'b' character in the second half (excluding middle point).
For odd length palindromes, changing the middle point will still yield a palindrome, so we must skip the midpoint. For odd length palindromes, the middle point is in between two chars, so we're good.

If first half of the string is all 'a', then changing any might give a non palindrome, however it won't be the lexicographically earliest, example: 'aa' could give 'ba' but the earliest is 'ab'

This means, if we can't change any 'a' from the left side, we must change the last char from the right to either 'a' or 'b' and will be left with the solution.

The only case where we can't give a solution at all is if the string only has one character, which is always a palindrome.

We can do this in O(N) time and space. The time is actually O(N/2) worst case, but we need to generate the new string, which requires us to copy the input somewhere where we can edit it, which costs O(N).

You can check my implementation of breakPalindrome on my Gist along with some tests in BreakPalindromeJTests.