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

public static string highestValuePalindrome(string s, int n, int k)
{
    if (k >= n)
    {
        var chars = Enumerable.Repeat('9', n).ToArray();
        return new string(chars);
    }

    if (n == 1 && k > 0) return "9";
    var InvRequiredIndexes = MinChangesMakingPalindrome(s);
    var setInvRequiredIndexes = InvRequiredIndexes.ToHashSet();
    var minChangesRequired = InvRequiredIndexes.Count;
    if (minChangesRequired > k) return "-1";
    var theChars = s.ToCharArray();
    if (minChangesRequired == k)
    {
        foreach (var i in InvRequiredIndexes)
        {
            if (theChars[i] > theChars[n - i -1]) theChars[n - i -1] = theChars[i];
            else theChars[i] = theChars[n - i -1];
        }
        return new string(theChars);
    }
    // k is > minChangesRequired
    var additionalChangesAvailable = k - minChangesRequired;
    while(additionalChangesAvailable > 0)
    {
        for (var i = 0; i < n / 2 && additionalChangesAvailable > 0; i++)
        {
            if (setInvRequiredIndexes.Contains(i)) // just 1 additional change needed
            {
                if(theChars[i] != '9' && theChars[n - i - 1] != '9') additionalChangesAvailable--;
                theChars[i] = theChars[n - i - 1] = '9';
                setInvRequiredIndexes.Remove(i);                        
            }
            else if(theChars[i] != '9' && additionalChangesAvailable >= 2)
            {
                theChars[i] = theChars[n - i - 1] = '9';
                additionalChangesAvailable -= 2;
            }
        }
        break;
    }

    // Done with the additional changes. Now cary out the mandatory changes if any left
    var lstInvRequiredIndexes = setInvRequiredIndexes.ToList();
    for (var i = 0; i < lstInvRequiredIndexes.Count; i++)
    {
        var ind = lstInvRequiredIndexes[i];
        if(additionalChangesAvailable > 0)
        {
            theChars[n - ind - 1] = theChars[ind] = '9';
            additionalChangesAvailable--;
        }
        else if (theChars[ind] < theChars[n - ind - 1]) theChars[ind] = theChars[n - ind - 1];
        else theChars[n - ind - 1] = theChars[ind];
    }
    if (n % 2 != 0 && additionalChangesAvailable > 0) theChars[n / 2] = '9';
    return new string(theChars);
}

public static List<int> MinChangesMakingPalindrome(string s)
{
    var len = s.Length;
    var halfLen = len / 2;
    var invIndexes = new List<int> { };
    for(var i = 0; i < halfLen; i++)
    {
        if (s[i] != s[len - i -1]) invIndexes.Add(i);
    }
    return invIndexes;
}