public static String highestValuePalindrome(String s, int n, int k) {
        int right = n/2 ; 
        int left = (n%2 == 0 ) ? (n-1)/2 : n/2;
        char[] c = s.toCharArray() ;

        // Tracking change indices.
        Set<Integer> changes = new HashSet<>();
        
        // Working out from the middle to generate the a Palindromes 
        while( left>=0 && right<c.length && k>=0 ) {
            if (c[left] != c[right] ) {
                // Found a none mathing pair, set to the max of either pair.
                c[left] = (char)Math.max(c[left], c[right]);
                c[right] = c[left];
                changes.add(left);
                --k;
            }
            --left;
            ++right;
        }
        
        // Working in form the ends
        while(k>0 && left < right) {
            ++left;
            --right;
            if (c[left] != '9') {
                if (changes.contains(left))
                    // Add back the original change to the change count.
                    ++k;
                if (left == right) {
                    // Handle special case.
                    c[left] = '9';
                    --k;
                } else if ( k>=2 ) {
                    c[left] = '9';
                    c[right] ='9';
                    k -= 2;                
                }
            }
        }
        
        return (k >= 0) ? new String(c) : "-1";
    }