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.

There is no reason to fiddle with individual digits when the only needed operation is one simple addition. The following code is based on Raks' answer.

The code stresses simplicity over execution speed, intentionally.

import static org.junit.Assert.assertEquals;

import java.math.BigInteger;
import org.junit.Test;

public class NextPalindromeTest {

    public static String nextPalindrome(String num) {
        int len = num.length();
        String left = num.substring(0, len / 2);
        String middle = num.substring(len / 2, len - len / 2);
        String right = num.substring(len - len / 2);

        if (right.compareTo(reverse(left)) < 0)
            return left + middle + reverse(left);

        String next = new BigInteger(left + middle).add(BigInteger.ONE).toString();
        return next.substring(0, left.length() + middle.length())
             + reverse(next).substring(middle.length());
    }

    private static String reverse(String s) {
        return new StringBuilder(s).reverse().toString();
    }

    @Test
    public void testNextPalindrome() {
        assertEquals("5", nextPalindrome("4"));
        assertEquals("11", nextPalindrome("9"));
        assertEquals("22", nextPalindrome("15"));
        assertEquals("101", nextPalindrome("99"));
        assertEquals("151", nextPalindrome("149"));
        assertEquals("123454321", nextPalindrome("123450000"));
        assertEquals("123464321", nextPalindrome("123454322"));
    }
}

Well I have constant order solution(atleast of order k, where k is number of digits in the number)

Lets take some examples suppose n=17208

divide the number into two parts from middle and reversibly write the most significant part onto the less significant one. ie, 17271 if the so generated number is greater than your n it is your palindrome, if not just increase the center number(pivot) ie, you get 17371

other examples

n=17286 palidrome-attempt=17271(since it is less than n increment the pivot, 2 in this case) so palidrome=17371

n=5684 palidrome1=5665 palidrome=5775

n=458322 palindrome=458854

now suppose n = 1219901 palidrome1=1219121 incrementing the pivot makes my number smaller here so increment the number adjacent pivot too 1220221

and this logic could be extended