public static String highestValuePalindrome(String s, int n, int k) {
        StringBuilder sb = new StringBuilder(s);
        Set<Integer> in = new HashSet<>();
        
        
        if(s.length() == 1) {
            return "9";
        }
        
        int total = n%2 ==0 ? n/2: n/2 + 1;
        
        for (int i = 0; i < total; i++) {
                if(sb.charAt(i) != sb.charAt(n - 1 -i)) {
                    if( k > 0) {
                        if( sb.charAt(i) > sb.charAt(n - 1 -i)) {
                            sb.setCharAt(n - 1 -i, sb.charAt(i));
                        } else {
                            sb.setCharAt(i, sb.charAt(n - 1 -i));
                        }
                        in.add(i);
                    } else {
                        return "-1";
                    }
                    k--;
                }
        }
        
        System.out.println("After Validation: " + k + " val: " + sb.toString());
        int j = 0;
        while(k > 0 && j < total) {
            
            if(sb.charAt(j) == '9') {
                j++;
                continue;
            }
            if(in.contains(j)) {
                sb.setCharAt(n - 1 - j, '9');
                sb.setCharAt(j, '9');
                k--;   
            } else {
                if(k == 1) {
                    j++;
                    continue;
                }
                sb.setCharAt(n - 1 -j, '9');
                sb.setCharAt(j, '9');
                k -= 2;
            }
            j++;
        }
        
        if(k > 0 && n%2 != 0) {
            sb.setCharAt(n/2, '9');
        }
        return sb.toString();
    }