public static String highestValuePalindrome(String s, int n, int k) {
        // Write your code here
        int max = n-1 ;
        int min = 0 ;
        char[] arr = s.toCharArray();
        boolean[] changeArr = new boolean[n];
        while(max >= min)
        {
            if(arr[max] != arr[min])
            {
                char maxChar = (char) Math.max(arr[max], arr[min]);
                arr[max] = arr[min] = maxChar ;
                k-- ;
                
                if(k < 0) return "-1";
                changeArr[max] = changeArr[min] = true ;
            }
            max-- ;
            min++ ;
        }
        
       
        
        // if still steps left maximize the string
        // Already changed in step 1, changing to '9' costs 1 more
        // Not changed before, changing both costs 2
        max = n-1 ;
        min = 0 ;
        while(k > 0  && min < max )
        {
            // Check if either of the digits at the current positions is not already '9'
            // If so, we can consider upgrading them to '9' to increase the value
            if (arr[min] != '9' || arr[max] != '9') 
            {
                if(changeArr[max] || changeArr[min] )
                {
                //if Already changed in step 1, changing to '9' costs 1 more
                    arr[max] = arr[min] =  '9' ;
                    k-- ;
                }else{
                    if(k >= 2) // if k =1 or zero we can't make 2 changes
                    {
                        arr[max] = arr[min] = '9';
                        k = k -2 ;
                    }
                }
                
            }
            
            
            max-- ;
            min++ ;
            
        }
        
         //change middel in odd in length
        if(k > 0)
        {
            if(n % 2 != 0 )
            {
                int mid = n / 2 ;
                arr[mid] = '9';
                k-- ;
            }
        }
        
        return new String(arr);

    }