public static String highestValuePalindrome(String s, int n, int k) {
    // Write your code here
    if(k == 0){
        //check if is palindrome
         if (new StringBuilder(s).reverse().toString().equals(s)) {
            return s;
        } else {
            return "-1";
        }
    }
    // we create a new string builder; this will have a length of n/2;
    StringBuilder sBuilder = new StringBuilder();
    // if k >= n, we can create 9999...99;    
    if(k >= n){
        String.join("", Collections.nCopies(n, "9"));
    }
    // explanation for the map; like a cost - if we want to change a digit
    // to 9, and still be palindrome, both digits must be 9, 
    // so there's a cost of 2.
    // if we already changed a digit at first step, to create the palindrome,
    // if we are left with extra moves after the palindrome has been created
    // we then can change one by one the digits that has already been changed
    // with a cost of 1 instead of 2.
    // E.G:  s = 1227, k = 2; => return 9229
    // we will want to make 9229, and the cost for that is 2,
    // but at first we dont know if we can create a palindrome with our k's,
    // so we start with that. After creating the palindrome, we can go back
    // and change 7227 to 9229.
    // at first, we change 1 to 7 so that we make palindrome: s=7227, k=1;
    // we can then change 7 to 9, to make the highest palindrome
    // because we still have k>0 after making it a palindrome,
    // we check at first digit. changing a digit except the middle one
    // means two digits must be changed, but because we already changed it
    // when creating the palindrome, we revert that change and instead
    // change both digits to be 9.
    
    //Map to know what digits have been changed once:
    Map<Integer, Integer> map = new HashMap<>();
    //check first digit
    System.out.println("length: " + n);
    int startIndex = 0;
    // check the first digit : if it's a 0, and the end is a 0 also,
    // we can't have an integer starting with 0, so we must change both.
    // if at the end is not 0, then we change the first to equal the last.
    if(s.charAt(0) == '0'){
        if(s.charAt(n-1) == '0') { k-=2; sBuilder.append('9');}
        else {k-=1; sBuilder.append(s.charAt(n-1));}
        map.put(0, n-1);   
        startIndex++;
    }
    
    
    if(k<0) { return "-1";}
    // we check each digit one by one
    for(int i=startIndex; i<n/2; i++){
        char start = s.charAt(i);
        char end = s.charAt(n-i-1);
        if(start == end){
            sBuilder.append(start);
        }
        
        else {
            if(k<=0) { return "-1";} // k < 0, no more changes available
            if(start - end > 0){
                sBuilder.append(start);
            
            }
            else { sBuilder.append(end);}
            map.put(i, n-i-1); // map it to know that it has been changed once
            k--; 
         }
    }
    
    // Maximize palindrome with '9's
    // start with j=-1 to correctly increment in the while
    // we increment first so that we are able to continue over the digits
    // to check if there are still digits with a "cost" of 1.
    int j=-1;
    while(k >= 1 && j<sBuilder.length()-1){
        j++;
        if(sBuilder.charAt(j) != '9'){
            
            if(map.containsKey(j)){ k-=1; }
            else{ 
                if(k<2) continue; 
                k-=2;
            }
            sBuilder.replace(j, j+1, "9");
        }
    }
    
    // the reversed half.
    StringBuilder reversed = new StringBuilder(sBuilder).reverse();
    // handle mid char - if length is odd; make it 9 if k>=1;
    if(n%2 == 1){
        char mid;
        if(k>=1){
            mid = '9';
        }
        else { mid = s.charAt(n/2);}
        return sBuilder.append(mid).append(reversed).toString();
    }
    
    return sBuilder.append(reversed).toString();
    
    }