In this post, we will solve Highest Value Palindrome HackerRank Solution. This problem (Highest Value Palindrome) is a part of HackerRank Problem Solving series.
Solution – Highest Value Palindrome – HackerRank Solution
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;
}
Python
import math
import os
import random
import re
import sys
# Complete the highestValuePalindrome function below.
def highestValuePalindrome(s, n, k):
min_no_of_changes = 0
for i in range(n//2):
if s[i] != s[n - i - 1]:
min_no_of_changes += 1
if min_no_of_changes > k:
return '-1'
highest_value_palindrome = ''
for i in range(n//2):
if k - min_no_of_changes > 1:
if s[i] != s[n - i - 1]:
if s[i] != '9' and s[n - i - 1] != '9':
highest_value_palindrome += '9'
k -= 2
else:
if s[i] > s[n - i - 1]:
highest_value_palindrome += s[i]
else:
highest_value_palindrome += s[n - i - 1]
k -= 1
min_no_of_changes -= 1
elif s[i] != '9': # s[i] is equal to s[n - i - 1]:
highest_value_palindrome += '9'
k -= 2
else:
highest_value_palindrome += s[i]
elif k - min_no_of_changes == 1:
if s[i] != s[n - i - 1]:
if s[i] != '9' and s[n - i - 1] != '9':
highest_value_palindrome += '9'
k -= 2
else:
if s[i] > s[n - i - 1]:
highest_value_palindrome += s[i]
else:
highest_value_palindrome += s[n - i - 1]
k -= 1
min_no_of_changes -= 1
else:
highest_value_palindrome += s[i]
elif s[i] != s[n - i - 1]: # in this case min_no_of_changes must equal to or less than k
if s[i] > s[n - i - 1]:
highest_value_palindrome += s[i]
else:
highest_value_palindrome += s[n - i - 1]
k -= 1
min_no_of_changes -= 1
else:
highest_value_palindrome += s[i]
if n&1:
if k > 0:
return highest_value_palindrome + '9' + highest_value_palindrome[::-1]
return highest_value_palindrome + s[n//2] + highest_value_palindrome[::-1]
return highest_value_palindrome + highest_value_palindrome[::-1]
if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')
nk = input().split()
n = int(nk[0])
k = int(nk[1])
s = input()
result = highestValuePalindrome(s, n, k)
fptr.write(result + '\n')
fptr.close()
Java
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
public class Solution {
public static void main(String[] args) {
Scanner reader = new Scanner(System.in);
int numberOfDigits = reader.nextInt();
int maximumDigitsToBeAltered = reader.nextInt();
String inputString = reader.next();
String result = richieRich(inputString, numberOfDigits, maximumDigitsToBeAltered);
System.out.println(result);
}
static String richieRich(String inputString, int numberOfDigits, int maximumDigitsToBeAltered) {
String palindrome = "";
int allDigitsWithoutNine = inputString.replaceAll("9", "").length();
if (allDigitsWithoutNine <= maximumDigitsToBeAltered) {
String regex = "[0-8]";
palindrome = inputString.replaceAll(regex, "9");
return palindrome;
}
StringBuilder strBuilder = new StringBuilder(inputString);
int nonMatches = 0;
for (int i = 0; i < numberOfDigits / 2; i++) {
int mirrorIndex = numberOfDigits - 1 - i;
if (strBuilder.charAt(i) != strBuilder.charAt(mirrorIndex)) {
nonMatches++;
}
}
int indexOfTransition = 0;
if (nonMatches < maximumDigitsToBeAltered) {
for (int i = 0; i < numberOfDigits / 2; i++) {
int mirrorIndex = numberOfDigits - 1 - i;
if (strBuilder.charAt(i) != '9' && strBuilder.charAt(mirrorIndex) != '9') {
if (strBuilder.charAt(i) != strBuilder.charAt(mirrorIndex)) {
nonMatches--;
}
if (nonMatches > maximumDigitsToBeAltered - 2) {
indexOfTransition = i;
break;
}
strBuilder.setCharAt(i, '9');
strBuilder.setCharAt(mirrorIndex, '9');
maximumDigitsToBeAltered -= 2;
if (nonMatches == maximumDigitsToBeAltered) {
indexOfTransition = i + 1;
break;
}
} else if (strBuilder.charAt(i) != strBuilder.charAt(mirrorIndex)) {
if (Character.getNumericValue(strBuilder.charAt(i)) > Character
.getNumericValue(strBuilder.charAt(mirrorIndex))) {
strBuilder.setCharAt(mirrorIndex, strBuilder.charAt(i));
maximumDigitsToBeAltered--;
nonMatches--;
} else {
strBuilder.setCharAt(i, strBuilder.charAt(mirrorIndex));
maximumDigitsToBeAltered--;
nonMatches--;
}
}
}
}
for (int i = indexOfTransition; i < numberOfDigits / 2; i++) {
int mirrorIndex = numberOfDigits - 1 - i;
if (strBuilder.charAt(i) != strBuilder.charAt(mirrorIndex)) {
if (Character.getNumericValue(strBuilder.charAt(i)) > Character
.getNumericValue(strBuilder.charAt(mirrorIndex))) {
strBuilder.setCharAt(mirrorIndex, strBuilder.charAt(i));
maximumDigitsToBeAltered--;
if (maximumDigitsToBeAltered == 0) {
break;
}
} else {
strBuilder.setCharAt(i, strBuilder.charAt(mirrorIndex));
maximumDigitsToBeAltered--;
if (maximumDigitsToBeAltered == 0) {
break;
}
}
}
}
if (!isPalindrome(strBuilder.toString())) {
return "-1";
}
if (strBuilder.toString().length() % 2 != 0
&& maximumDigitsToBeAltered>0) {
int midIndex = strBuilder.toString().length() / 2;
if (strBuilder.charAt(midIndex) != '9') {
strBuilder.setCharAt(midIndex, '9');
}
}
palindrome = strBuilder.toString();
return palindrome;
}
public static boolean isPalindrome(String inputString) {
StringBuilder strBuilder = new StringBuilder(inputString);
if (strBuilder.reverse().toString().equals(inputString)) {
return true;
}
return false;
}
}
Note: This problem (Highest Value Palindrome) is generated by HackerRank but the solution is provided by CodingBroz. This tutorial is only for Educational and Learning purpose.