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.

HackerRank Highest Value Palindrome problem solution


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}