**C# Solution O(n) time 0(1) space **

public static string highestValuePalindrome(string s, int n, int k)
{
    /* Thought process
    if s is palindrome, then easily update
    if s is not palindrome, then need to know how many different pair D.
    If k < D, then nope. Otherwise,
    If k == D, change all half of the diff pairs
    if k > D, after above, change from the furthest out pair to inside
    */
    char[] arr = s.ToArray<char>();
    HashSet<int> updated = new HashSet<int>();
    int l = 0, r = n-1;
    int mid = n/2;
    int replace = k;
    while ( l < r) {
        if (s[l] == s[r]) { 
            l++; r--;
            continue;
        } 
        if (replace>0) {
            if (s[l] > s[r]) {
                arr[r] = arr[l];
            } else {
                arr[l] = arr[r];
            }
            updated.Add(l);
            replace--;
        } else {
            if (l < mid) {
                return "-1";
            }
        }
        l++; r--;
    } 
    l = 0;
    r = n-1;
    while(replace > 0 && l<=r) {
        if (arr[l]<'9') {
            if (l == r) {
                arr[l] = '9';
                break;
            }
            if (updated.Contains(l)) {
                // need one change only, since one is counted to update to non-9
                arr[l] = '9';
                arr[r] = '9';
                replace--;
            } else if (replace > 1) {
                arr[l] = '9';
                arr[r] = '9';
                replace-=2;
            }
        }
        l++; r--;
    }

    return new string(arr);