SPOJ The Next Palindrome Solution in Java

Solved this problem with the help of BigInt as well, but gave TLE.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    public static char[] getNextNum(char[] a) {
        boolean carry = true;
        for (int i = a.length - 1; i >= 0; i--) {
            if (!carry) break;

            if (a[i] == '9') {
                carry = true;
                a[i] = '0';
            } else {
                a[i] = (char) (a[i] + 1);
                carry = false;
            }
        }
        char[] b;
        if (carry) {
            b = new char[a.length + 1];
            b[0] = '1';
            for (int i = 0; i < a.length; i++) {
                b[i + 1] = a[i];
            }
        } else {
            b = a;
        }
        return b;
    }

    public static int compare(char[] a, char[] b) {
        if (a.length < b.length) return -1;
        if (a.length > b.length) return 1;
        for (int i = a.length - 1; i >= 0; i--) {
            if (a[i] > b[i]) return 1;
            if (a[i] < b[i]) return -1;
        }
        return 0;
    }

    public static boolean isPalindrome(char[] a) {
        for (int i = 0; i < a.length / 2; i++) {
            if (a[i] != a[a.length - i - 1]) return false;
        }
        return true;
    }

    public static char[] reverse(char[] a) {
        char[] b = new char[a.length];
        for (int i = 0; i < a.length; i++) {
            b[i] = a[a.length - i - 1];
        }
        return b;
    }

    public static char[] subArray(char[] a, int x, int y) {
        char[] b = new char[y - x];
        for (int i = x; i < y; i++) {
            b[i - x] = a[i];
        }
        return b;
    }

    public static class InputReader {
        private BufferedReader reader;
        private StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream));
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }
    }

    public static void main(String[] args) {
        InputReader in = new InputReader(System.in);
        int T = in.nextInt();
        while (T-- != 0) {
            String num = in.next();

            if (num.length() == 1) {
                System.out.println(11);
                continue;
            }

            char[] a = num.toCharArray();
            a = getNextNum(a);
            if (isPalindrome(a)) {
                System.out.println(a);
                continue;
            }

            if (a.length % 2 == 0) {
                char[] pre = subArray(a, 0, a.length / 2);
                char[] post = subArray(a, a.length / 2, a.length);

                if (compare(post, reverse(pre)) > 0) {
                    pre = getNextNum(pre);
                }

                System.out.print(pre);
                System.out.println(reverse(pre));
            } else {
                char[] pre = subArray(a, 0, a.length / 2 + 1);
                char[] post = subArray(a, a.length / 2 + 1, a.length);

                char[] evenPart = subArray(pre, 0, pre.length - 1);
                if (compare(post, reverse(evenPart)) > 0) {
                    pre = getNextNum(pre);
                }
                System.out.print(pre);
                System.out.println(reverse(subArray(pre, 0, pre.length - 1)));
            }

        }
    }
}