Next higher palindromic number using the same set of digits

import java.io.*;
import java.util.*;

class GfG
{
    public static void main(String args[])
    {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while(t-->0)
        {
            String s = sc.next();
            Solution obj = new Solution();
            System.out.println(obj.nextPalin(s));
        
System.out.println("~");
}
            
    }
}

class Solution
{
    public String nextPalin(String N) 
    { 
        //complete the function here
        //Step 1: Take first half of string
        int len = N.length();
        //edge cases
        
        String midDigit = (len%2!=0) ? N.charAt(len/2) + "" : "" ;
        String half = N.substring(0,len/2);
        //Step 2: Find the next bigger number for the half.
        StringBuilder sb = nextBigger(half);
        //Step 3: If result exists return palindrome of string else -1.
        if(sb.length()==0) return "-1";
        
        String reverse = new StringBuilder(sb).reverse().toString();
        return sb + midDigit + reverse;
    }
    
    private StringBuilder nextBigger(String half){
        char[] charray = half.toCharArray();
        int[] count = new int[10];
        //2a. Find first digit from end which is not in strict increasing order. We now work in this set of digits.
        //x y digit m
        int pos=charray.length - 1;
        int digit = 0;
        for(;pos>=0;pos--){
            int currentDigit = Character.digit(charray[pos],10);
            count[currentDigit]++;
            if(digit > currentDigit){
                digit = currentDigit;
                break;
            }
            digit = currentDigit;
        }
        
        if(pos == -1) return new StringBuilder();
        
	    //2b. Find next bigger digit than first digit
	    for(int val = digit+1; val<10; val++){
	        if(count[val] > 0){
	            count[val]--;
	            charray[pos] = Character.forDigit(val, 10);
	            pos++;
	            break;
	        }
	    }
	    
	    //2c. Make smallest number out of remaining digits
	    for(int val = 0; val<10; val++){
	        while(count[val]>0){
	            count[val]--;
	            charray[pos] = Character.forDigit(val, 10);
	            pos++;
	        }
	    }
	    
	    return new StringBuilder(new String(charray));
	    
	 }
}