**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);

Hi @nabila_ahmed

You are the author of Highest Value Palindrome problem. I was going through your solution and in your condition below condition else if((mark[l]==1 || mark[r]==1) && k>=1) { k-=1; ans[l] = ans[r] = '9'; } You are decrementing k by 1 but it should be decremented by 2 because we are changing both ans[l] and ans[r] in theelse part which requires 2 moves. If only 1 move is left how is this condition justified!!!

@Xromeo

I saw your solution in JAVA but I have a thing to ask..in the below condition else if (k - changes >= 1 && s.charAt(left) != s.charAt(right)) {

                    chars[left] = '9';
                    chars[right] = '9';
                    changes++;
                }

In this condition, you are changing two characters but incrementing changes by 1. Why? For the string "092282" with k = 3, I debugged the code and in first loop the array was [2, 9, 2, 2, 9, 2] but in the above condition you are actually changing the values of both left and right index but incrementing the change by 1. I think it should be 2 . Am I mising something in the logic?

My answer with Typescript, simple

function highestValuePalindrome(s: string, n: number, k: number): string {
    const replace = (s: string, i: number, c: string): string => {
        return s.substring(0, i) + c + s.substring(i + 1)
    }

    // 1. make [s] palidrome (required [k*] number of times), mark [i] that need to changes
    //  - using larger value to replace, saving [k] in 2. step
    let circles = []
    for (let i = 0; i < Math.floor(n / 2); i++) {
        let j = n - i - 1

        if (s[i] == s[j]) continue

        if (s[i] > s[j]) s = replace(s, j, s[i])
        if (s[i] < s[j]) s = replace(s, i, s[j])

        k--
        circles.push(i)

        // no more [k] left, it can't be palidrome
        if (k < 0) return '-1'
    }

    // 2. with remaining [k], replacement to increasing number value
    //  - with [i] that marked only need changes 1 orelse 2
    //  - with [s] is odd, changes the middle number if still have [k]
    for (let i = 0; i < Math.floor(n / 2); i++) {
        let j = n - i - 1

        if (s[i] != '9') {
            let k_ = circles.includes(i) ? 1 : 2
            if (k >= k_) {
                s = replace(s, i, '9')
                s = replace(s, j, '9')
                k -= k_
            }
        }

    }
    if (n % 2 == 1 && k > 0) s = replace(s, Math.floor(n / 2), '9')
    
    // 3. return the final palidrome [s]
    return s
}