Лучший алгоритм для поиска следующего палиндрома числовой строки

Во-первых, вот проблема:

Положительное целое число называется палиндромом, если его представление в десятичной системе одинаково при чтении слева направо и справа налево. Для данного положительного целого числа K, состоящего не более чем из 1000000 цифр, запишите для вывода значение наименьшего палиндрома, превышающего K. Числа всегда отображаются без ведущих нулей.

Входные данные: первая строка содержит целое число t - количество тестов. В следующих t строках даны целые числа K.

Выходные данные: для каждого K выведите наименьший палиндром, больший, чем K. Пример

Входные данные:

2

808

2133

Выходные данные:

818

2222

Во-вторых, вот мой код:

// I know it is bad practice to not cater for erroneous input,
// however for the purpose of the execise it is omitted
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Scanner;
import java.lang.Exception;
import java.math.BigInteger;

public class Main
{    
    public static void main(String [] args){   
        try{
            Main instance = new Main(); // create an instance to access non-static
                                        // variables

            // Use java.util.Scanner to scan the get the input and initialise the
            // variable
            Scanner sc=null;

            BufferedReader r = new BufferedReader(new InputStreamReader(System.in));

            String input = "";

            int numberOfTests = 0;

            String k; // declare any other variables here

            if((input = r.readLine()) != null){
                sc = new Scanner(input);
                numberOfTests = sc.nextInt();
            }

            for (int i = 0; i < numberOfTests; i++){
                if((input = r.readLine()) != null){
                    sc = new Scanner(input);
                    k=sc.next(); // initialise the remainder of the variables sc.next()
                    instance.palindrome(k);
                } //if
            }// for
        }// try

        catch (Exception e)
        {
            e.printStackTrace();
        }
    }// main

    public void palindrome(String number){

        StringBuffer theNumber = new StringBuffer(number);
        int length = theNumber.length();
        int left, right, leftPos, rightPos;
        // if incresing a value to more than 9 the value to left (offset) need incrementing
        int offset, offsetPos;
        boolean offsetUpdated;
        // To update the string with new values
        String insert;
        boolean hasAltered = false;

        for(int i = 0; i < length/2; i++){
            leftPos = i; 
            rightPos = (length-1) - i;
            offsetPos = rightPos -1; offsetUpdated = false;

            // set values at opposite indices and offset
            left = Integer.parseInt(String.valueOf(theNumber.charAt(leftPos)));
            right = Integer.parseInt(String.valueOf(theNumber.charAt(rightPos)));
            offset = Integer.parseInt(String.valueOf(theNumber.charAt(offsetPos)));

            if(left != right){
                // if r > l then offest needs updating
                if(right > left){
                    // update and replace
                    right = left;
                    insert = Integer.toString(right);

                    theNumber.replace(rightPos, rightPos + 1, insert);

                    offset++; if (offset == 10) offset = 0;
                    insert = Integer.toString(offset);

                    theNumber.replace(offsetPos, offsetPos + 1, insert);
                    offsetUpdated = true;

                    // then we need to update the value to left again
                    while (offset == 0 && offsetUpdated){ 
                        offsetPos--;
                        offset =
                            Integer.parseInt(String.valueOf(theNumber.charAt(offsetPos)));
                        offset++; if (offset == 10) offset = 0;
                        // replace
                        insert = Integer.toString(offset);
                        theNumber.replace(offsetPos, offsetPos + 1, insert);
                    }
                    // finally incase right and offset are the two middle values
                    left = Integer.parseInt(String.valueOf(theNumber.charAt(leftPos)));
                    if (right != left){
                        right = left;
                        insert = Integer.toString(right);
                        theNumber.replace(rightPos, rightPos + 1, insert);
                    }
                }// if r > l
                else
                    // update and replace
                    right = left;
                    insert = Integer.toString(right);
                    theNumber.replace(rightPos, rightPos + 1, insert);           
            }// if l != r
        }// for i
        System.out.println(theNumber.toString());
    }// palindrome
}

Наконец, мое объяснение и вопрос.

My code compares either end and then moves in
    if left and right are not equal
        if right is greater than left
            (increasing right past 9 should increase the digit
             to its left i.e 09 ---- > 10) and continue to do
             so if require as for 89999, increasing the right
             most 9 makes the value 90000

             before updating my string we check that the right
             and left are equal, because in the middle e.g 78849887
             we set the 9 --> 4 and increase 4 --> 5, so we must cater for this.

Проблема исходит от spoj.pl, онлайн-системы судейства. Мой код работает для всего теста, который может предоставить, но когда я отправляю его, я получаю ошибку превышения лимита времени, и мой ответ не принимается.

Есть ли у кого-нибудь предложения, как я могу улучшить свой алгоритм. При написании этого вопроса я подумал, что вместо цикла while (offset == 0 && offsetUpdated) я мог бы использовать логическое значение, чтобы убедиться, что я увеличиваю смещение на следующей [i] итерации. Мы будем благодарны за подтверждение моего изменения или любое предложение, также дайте мне знать, если мне нужно сделать свой вопрос более ясным.