# HackerRank Highest Value Palindrome problem solution

In this HackerRank Highest Value Palindrome problem solution we have given a string representing the starting number, and a maximum number of changes allowed, create the largest palindromic string of digits possible or the string '-1' if it is not possible to create a palindrome under the constraints.

## Problem solution in Python.

```#!/bin/python3
from sys import exit
from math import floor
n, k = map(int, input().split())
num = list(input().strip())
unpaired = len(list(filter(lambda x: x[0] != x[1], zip(num[:int(floor(n / 2))], reversed(num)))))
if unpaired > k:
print(-1)
exit()
for i in range(int(floor(n / 2))):
if unpaired < k and k >= 2:
if num[i] != num[n - 1 - i]:
unpaired -= 1
if num[i] != '9':
k -= 1
if num[n - 1 - i] != '9':
k -= 1
num[i] = num[n - 1 - i] = '9'
continue
if num[i] == num[n - 1 - i]:
continue
k -= 1
if k < 0:
break
num[i] = max(num[i], num[n - 1 - i])
num[n - 1 - i] = num[i]
if k > 0 and n % 2 == 1:
num[int(floor(n / 2))] = '9'
print(-1 if k < 0 else ''.join(num))```

{"mode":"full","isActive":false}

## Problem solution in Java.

```import java.io.*;
import java.util.*;

public class Solution {

public static void main(String[] args) {
/* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */

Scanner scan = new Scanner(System.in);
int N = scan.nextInt();
int max = scan.nextInt();
scan.nextLine();
StringBuilder input = new StringBuilder(scan.nextLine());
input.setLength(N);
input.trimToSize();
int need = 0;
for(int i=0;i<N/2;i++){
char left = input.charAt(i);
char right=input.charAt(N-1-i);
if(left!=right)
need++;
}
if(need > max){
System.out.println(-1);
}else{
int free = max - need;
for(int i=0;i<N/2;i++){
char left = input.charAt(i);
char right=input.charAt(N-1-i);
if(free>=2){
if(left!=right)
free++;
if(left!='9'){
input.setCharAt(i, '9');
free--;
}
if(right!='9'){
input.setCharAt(N-1-i, '9');
free--;
}
}else if(free==1){
if(left!=right){
if(left=='9'||right=='9')
free++;
if(left!='9'){
input.setCharAt(i, '9');
free--;
}
if(right!='9'){
input.setCharAt(N-1-i, '9');
free--;
}
}
}else{
if(left!=right){
if(left>right)
input.setCharAt(N-1-i, left);
else {
input.setCharAt(i, right);
}
}
}
}
if(N%2==1&&free>0)
input.setCharAt(N/2, '9');
System.out.println(input);
}

scan.close();
}
}```

{"mode":"full","isActive":false}

## Problem solution in C++.

```#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

int main() {
/* Enter your code  here. Read input from STDIN. Print output to STDOUT */
int n,k;
cin>>n>>k;
string str;
cin>>str;
bool ok =true;
int c = 0;
for(int i=0;i<n/2;i++){
if(str[i]!=str[n-i-1])c++;
}
if(c > k){
cout<<-1<<endl;
return 0;
}
for(int i=0;i<n/2;i++){
if(str[i]!=str[n-i-1]){
if(max(str[i] ,str[n-i-1]) == '9') {
str[i] = str[n-i-1] = '9'; k--; c--;
}
else if(k > c){
str[i] = str[n-i-1] = '9'; k-=2; c--;
}
else{
str[i] = str[n-i-1] =max(str[i] ,str[n-i-1]) ; k--; c--;
}
}else{
if(max(str[i] ,str[n-i-1]) == '9') {
continue;
}
else if(k > c+1){
str[i] = str[n-i-1] = '9'; k-=2;
}
}
}

if(k && n%2==1) str[n/2] = '9';
cout<<str<<endl;
return 0;
}
```

{"mode":"full","isActive":false}

## Problem solution in C.

```#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <limits.h>
#include <stdbool.h>

int main(){
int n;
int k;
scanf("%d %d",&n,&k);
getchar();
char* number = (char *)malloc(10240 * sizeof(char));
scanf("%s",number);
int c=0;
int i;
int flag[100005];
for(i=0;i<n/2;i++){
if(c<k){
if(number[i]!=number[n-i-1]){
if(number[i]>number[n-i-1]){
number[n-i-1]=number[i];
}
else{
number[i]=number[n-i-1];
}
flag[i]=flag[n-i-1]=1;
c++;
}
}
else{
if(number[i]!=number[n-i-1])
break;
else
{}
}
}
if(c<k){
int j=0;
while(k-c>=2&&j<n/2){
if(number[j]!='9'){
if(flag[j]==1){
number[j]='9';
number[n-j-1]='9';
c++;
}
else{
number[j]='9';
number[n-j-1]='9';
c+=2;
}
}
j++;
}
for(int i=0;i<n/2;i++){
if(number[i]!='9'&&flag[i]==1&&c<k){
number[i]='9';
number[n-i-1]='9';
c++;
}
}
if(n%2==1&&c<k){
number[n/2]='9';
c++;
}
}
if(i<n/2){
printf("-1\n");
}
else{
printf("%s\n",number);
}
return 0;
}
```

{"mode":"full","isActive":false}