HackerRank Highest Value Palindrome problem solution

In this HackerRank Highest Value Palindrome problem solution, Palindromes are strings that read the same from the left or right, for example madam or 0110.

You will be given a string representation of a number and a maximum number of changes you can make. Alter the string, one digit at a time, to create the string representation of the largest number possible given the limit to the number of changes. The length of the string may not be altered, so you must consider ‘s left of all higher digits in your tests. For example 0110 is valid, 0011 is not.

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 contstraints.

Function Description

Complete the highestValuePalindrome function in the editor below.

highestValuePalindrome has the following parameter(s):

• string s: a string representation of an integer
• int n: the length of the integer string
• int k: the maximum number of changes allowed

Returns

• string: a string representation of the highest value achievable or -1

HackerRank Highest Value Palindrome 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))

Highest Value Palindrome 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();
    }
}

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;
}

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("-1n");
    }
    else{
        printf("%sn",number);
    }
    return 0;
}