A better algorithm to find the next palindrome of a number string

This seems like a lot of code. Have you tried a very naive approach yet? Checking whether something is a palindrome is actually very simple.

private boolean isPalindrome(int possiblePalindrome) {
    String stringRepresentation = String.valueOf(possiblePalindrome);
    if ( stringRepresentation.equals(stringRepresentation.reverse()) ) {
       return true;
    }
}

Now that might not be the most performant code, but it gives you a really simple starting point:

private int nextLargestPalindrome(int fromNumber) {
    for ( int i = fromNumber + 1; ; i++ ) {
        if ( isPalindrome( i ) ) {
            return i;
        }
    }
}

Now if that isn’t fast enough you can use it as a reference implementation and work on decreasing the algorithmic complexity.

There should actually be a constant-time (well it is linear on the number of digits of the input) way to find the next largest palindrome. I will give an algorithm that assumes the number is an even number of digits long (but can be extended to an odd number of digits).

1. Find the decimal representation of the input number (“2133”).
2. Split it into the left half and right half (“21”, “33”);
3. Compare the last digit in the left half and the first digit in the right half.
   a. If the right is greater than the left, increment the left and stop. (“22”)
   b. If the right is less than the left, stop.
   c. If the right is equal to the left, repeat step 3 with the second-last digit in the left and the second digit in the right (and so on).
4. Take the left half and append the left half reversed. That’s your next largest palindrome. (“2222”)

Applied to a more complicated number:

1.    1234567887654322
2.    12345678   87654322
3.    12345678   87654322
             ^   ^         equal
3.    12345678   87654322
            ^     ^        equal
3.    12345678   87654322
           ^       ^       equal
3.    12345678   87654322
          ^         ^      equal
3.    12345678   87654322
         ^           ^     equal
3.    12345678   87654322
        ^             ^    equal
3.    12345678   87654322
       ^               ^   equal
3.    12345678   87654322
      ^                 ^  greater than, so increment the left

3.    12345679

4.    1234567997654321  answer

This seems a bit similar to the algorithm you described, but it starts at the inner digits and moves to the outer.