java solution: All test cases passed.

public static String highestValuePalindrome(String s, int n, int k) { // Write your code here

int left=0;
int right=n-1;
List<Integer> list=new ArrayList<>();
char[] a=s.toCharArray();
if(n==1&k>0){
    return "9";
}
if(k>=n){
    Arrays.fill(a,'9');
    return String.valueOf(a);
}
while(left<right){
    if(a[left]!=a[right]){
        count++;
   if(k>=1 && a[left]>a[right]){
       a[right]=a[left];
       k--;

       list.add(right);
   } 
   else if(k>=1&&a[right]>a[left]){
   a[left]=a[right];
   list.add(left);
   k--;
   }
    }
   if(k<1 &&a[left]!=a[right])
   return "-1";
   left++;
   right--;
}


int i=0;
int j=n-1;
while(i<j){
    if((list.contains(i)||list.contains(j))&&k>=1 && a[i]!='9'){
        a[i]='9';
        a[j]='9';
        k--;
    }
    else if(!list.contains(i)&&!list.contains(j)&&k>=2 && a[i]!='9'){
        a[i]='9';
        a[j]='9';
        k=k-2;
    }
    if(k==0 && a[i]!=a[j]){
        return "-1";
    }
    i++;
    j--;
}
if(i==j&&k>=1){
    a[i]='9';
}
return String.valueOf(a);

}