def highestValuePalindrome(s, n, k):
    # Convert the string to a mutable list
    s = list(s)
    # Step 1: Identify mismatched mirrored pairs
    mismatches = []
    for i in range(n // 2):
        if s[i] != s[n - i - 1]:
            mismatches.append((i, n - i - 1))

    # Step 2: Check if we have enough changes to fix all mismatches
    if len(mismatches) > k:
        return "-1"  # Not enough changes to make it a palindrome

    # Step 3: Fix mismatched mirrored pairs
    for i, j in mismatches:
        # Use the larger of the two digits to fix the mismatch
        s[i] = s[j] = max(s[i], s[j])
        k -= 1  # Count this as one change

    # Step 4: Maximize the palindrome using remaining changes
    for i in range(n // 2):
        if k <= 0:
            break

        # If the current pair is not already '9', we can try to maximize it
        if s[i] != '9':
            # If this pair was previously fixed, it costs 1 change
            if (i, n - i - 1) in mismatches:
                s[i] = s[n - i - 1] = '9'
                k -= 1
            # If this pair was already a match, it costs 2 changes
            elif k >= 2:
                s[i] = s[n - i - 1] = '9'
                k -= 2

    # If the string has an odd length, we can change the middle character
    if n % 2 == 1 and k > 0:
        s[n // 2] = '9'

    # Return the resulting palindrome
    return ''.join(s)

    public static String highestValuePalindrome(String s, int n, int k) {
        int right = n/2 ; 
        int left = (n%2 == 0 ) ? (n-1)/2 : n/2;
        char[] c = s.toCharArray() ;

        // Tracking change indices.
        Set<Integer> changes = new HashSet<>();
        
        // Working out from the middle to generate the a Palindromes 
        while( left>=0 && right<c.length && k>=0 ) {
            if (c[left] != c[right] ) {
                // Found a none mathing pair, set to the max of either pair.
                c[left] = (char)Math.max(c[left], c[right]);
                c[right] = c[left];
                changes.add(left);
                --k;
            }
            --left;
            ++right;
        }
        
        // Working in form the ends
        while(k>0 && left < right) {
            ++left;
            --right;
            if (c[left] != '9') {
                if (changes.contains(left))
                    // Add back the original change to the change count.
                    ++k;
                if (left == right) {
                    // Handle special case.
                    c[left] = '9';
                    --k;
                } else if ( k>=2 ) {
                    c[left] = '9';
                    c[right] ='9';
                    k -= 2;                
                }
            }
        }
        
        return (k >= 0) ? new String(c) : "-1";
    }

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();
    
    }