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
}