string highestValuePalindrome(string s, int n, int k) 
{
    int i = 0;
    std::set< int > visited;
    
    while ( i < s.size() )
    {
        if ( s[ i ] != s[ n - i - 1 ] )
        {
            if ( k == 0 ) return "-1";
            auto value = std::max( s[ i ], s[ n - i - 1 ] );
            s[ i ] = s[ n - i - 1 ] = value;
            k--;
            visited.insert( i );
        }
        i++;
    }

    // in here s is a palindrome

    i = 0;
    while ( i < s.size() && k > 0 )
    {
        if ( s[ i ] != '9' )
        {
            if ( visited.find( i ) != visited.end() )
            {
                s[ i ] = s[ n - i - 1 ] = '9';
                k--;
            }
            else if ( k >= 2 )
            {
                s[ i ] = s[ n - i - 1 ] = '9';
                k -= 2;
            }
        }
        
        i++;
    }
    
    if ( n % 2 == 1 && k > 0 ) s[ n/2 ] = '9';

    return s;
}

string highestValuePalindrome(string s, int n, int k) {
    
    // change to true when the 's' is checked to be a valid palindrome
    bool isValid = false;
    // mark touched[i] to true if s[i] is changed. thus 
    // we can change s[i] again and again and still use up only one k
    vector<bool> touched(n, false);
    
    // 1st round - use k to turn 's' into valid palindrome
    int l=0, r=s.size()-1; // the right and left index to s
    while (k>=0 and l<=r) {
        // whenever s[l]] != s[r], one of them need to changed
        // always change the smaller digit to the larger one
        if (s[l] != s[r]) {
            char largerCh = max(s[l], s[r]);
            touched[l] = largerCh != s[l];
            touched[r] = largerCh != s[r];
            s[l] = largerCh;
            s[r] = largerCh;
            --k;
        }
        ++l;
        --r;
    }
    isValid = l>r and k>=0;
    cout << "after 1st round - " << s << endl;
    
    // 2nd round - use remaining k to maximize 's'
    l=0;
    r=s.size()-1;
    int kToUse = 0;
    while (isValid and k>=0 and l<=r) {
        // change MSB to '9' whenever we still have k to use
        // note change we can also change s[i] without using any k
        // if touched[i] is true. also if s[i] is already '9' we 
        // don't need to change it any bigger
        
        kToUse = 0;
        kToUse += (s[l] != '9') and (not touched[l]);
        kToUse += (r != l) and (s[r] != '9') and (not touched[r]);     
        if (k >= kToUse) {
            s[l] = '9';
            s[r] = '9'; 
            k -= kToUse;
        }
        ++l;
        --r;
    }
    
    if (isValid) return s;
    else return "-1";
}

def highestValuePalindrome(s, n, k):
    # Write your code here
    # Check minimum number of changes needed to make it a palindrome
    min_count = 0
    min_change_index_list = []
    for i in range(n // 2):
        if s[i] != s[-1 - i]:
            min_count += 1
            min_change_index_list.append(i)
    if min_count > k:
        return "-1"

    # Make it with the minimum number of changes
    s = list(s)
    for i in min_change_index_list:
        s[i] = s[-1 - i] = max(s[i], s[-1 - i])

    # Return immediately if min_count == k
    if min_count == k:
        return "".join(s)

    # Make it with the maximum number of changes
    # Get index for making highest value
    max_change_index_list = []
    max_count = k - min_count
    for i in range(n // 2):
        if max_count == 0:
            break
        if s[i] != "9" and s[-1 - i] != "9":
            if i in min_change_index_list:
                max_count -= 1
                max_change_index_list.append(i)
            elif max_count >= 2:
                max_change_index_list.append(i)
                max_count -= 2
    for i in max_change_index_list:
        s[i] = s[-1 - i] = "9"
    if n % 2 == 1 and max_count > 0:
        s[n // 2] = "9"
    return "".join(s)