My code does not use the typical two phase approach. It finish the changes in one sweep.

def highestValuePalindrome(s, n, k): # Write your code here

N = len(s)
s = list(s)

imbalance = 0

for i in range(N//2):
    if s[i] != s[N-1-i]:
        imbalance += 1

if k < imbalance:
    return '-1'

if N % 2 == 1:
    limit = N//2 + 1
else:
    limit = N//2

for i in range(limit):

    if s[i] == '9' and s[N-i-1] == '9': # Best scenario, nothing to do.
        continue

    if s[i] == s[N-1-i] and k >= imbalance + 2: #If there is budget, change both at the cost of losing two counts in the budget and no reduction in imbalance.
        s[i] = '9'
        s[N-i-1] = '9'
        k -= 2
    elif s[i] != s[N-1-i] and (s[i]=='9' or s[N-1-i]=='9'): #if not balanced, but one of them is 9, cost one count in budget and reduce imbalance by 1.
        s[i] = '9'
        s[N-i-1] = '9'
        k -= 1
        imbalance -= 1
    elif s[i] != s[N-1-i] and k >= imbalance + 1: # if both are not 9 and not balanced, change both to 9 only when there is budget.
        s[i] = '9'
        s[N-i-1] = '9'
        k -= 2
        imbalance -= 1
    elif s[i] != s[N-1-i]: # typical change
        if s[i] > s[N-i-1]:
            s[N-i-1] = s[i]
        else:
            s[i] = s[N-i-1]
        k -= 1
        imbalance -= 1
    elif k > 0 and imbalance == 0 and N % 2 ==1:
        s[N//2] = '9'

return ''.join(s)