# Hackerrank Highest Value Palindrome Solution

.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue} .MathJax_SVG_LineBox {display: table!important} .MathJax_SVG_LineBox span {display: table-cell!important; width: 10000em!important; min-width: 0; max-width: none; padding: 0; border: 0; margin: 0}

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  is valid,  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's impossible to create a palindrome under the contstraints.

Function Description

Complete the highestValuePalindrome function in the editor below.  It should return a string representing the largest value palindrome achievable, or -1.

highestValuePalindrome has the following parameter(s):

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

Input Format.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue} .MathJax_SVG_LineBox {display: table!important} .MathJax_SVG_LineBox span {display: table-cell!important; width: 10000em!important; min-width: 0; max-width: none; padding: 0; border: 0; margin: 0}

The first line contains two space-separated integers,  and , the number of digits in the number and the maximum number of changes allowed.
The second line contains an -digit string of numbers.

Constraints.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue}

• Each character  in the number is an integer where .

Output Format.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue} .MathJax_SVG_LineBox {display: table!important} .MathJax_SVG_LineBox span {display: table-cell!important; width: 10000em!important; min-width: 0; max-width: none; padding: 0; border: 0; margin: 0}

Print a single line with the largest number that can be made by changing no more than  digits. If this is not possible, print -1.

Sample Input 0

4 1
3943


Sample Output 0

3993


Sample Input 1

6 3
092282


Sample Output 1

992299


Sample Input 2

4 1
0011


Sample Output 2

-1


Explanation.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue} .MathJax_SVG_LineBox {display: table!important} .MathJax_SVG_LineBox span {display: table-cell!important; width: 10000em!important; min-width: 0; max-width: none; padding: 0; border: 0; margin: 0}

Sample 0

There are two ways to make  a palindrome by changing no more than  digits:

, so we print .

### Solution in java8

Approach 1.

import java.util.Scanner;

/**
* https://www.hackerrank.com/challenges/richie-rich
*/
public class RichieRich {
private static String largestPalindrome(String number, int k) {
char[] chars = number.toCharArray();
int minChange = 0;
for (int i = 0, j = chars.length - 1; i < j; i++, j--) {
if (chars[i] != chars[j]) {
minChange++;
}
}
if (minChange > k) {
return "-1";
}
int changeBoth = k - minChange;
int i = 0;
int j = chars.length - 1;
for (; i <= j; i++, j--) {
if (chars[i] != chars[j]) {
char maxChar = (char) Math.max(chars[i], chars[j]);
if (maxChar != '9' && changeBoth - 1 >= 0) {
chars[i] = '9';
chars[j] = '9';
changeBoth--;
} else {
chars[i] = maxChar;
chars[j] = maxChar;
minChange--;
}
} else {
char maxChar = (char) Math.max(chars[i], chars[j]);
if (maxChar != '9' && changeBoth - 2 >= 0) {
chars[i] = '9';
chars[j] = '9';
changeBoth -= 2;
}
}
}
if (changeBoth != 0 && i - 1 == j + 1) {
chars[i - 1] = '9';
}
String palindrome = new String(chars);
return palindrome;
}

public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int k = in.nextInt();
String number = in.next();
System.out.println(largestPalindrome(number, k));
}
}


Approach 2.

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;

public class Solution {
public static void main(String args[]){
Scanner scanner = new Scanner(System.in);

int n = scanner.nextInt();
int k = scanner.nextInt();
char[] c = scanner.next().toCharArray();
boolean[] ch = new boolean[n];
for (int i = 0; i < n/2; ++i) {
if (c[i] != c[n - i - 1]) {
c[i] = c[n - i - 1] = (char)Math.max(c[i], c[n - i - 1]);
ch[i] = true;
--k;
}
}
if (k < 0) {
System.out.println(-1);
return;
}
for (int i = 0; i < n/2; ++i) {
if (c[i] != '9') {
if (ch[i] && k > 0) {
c[i] = c[n - i - 1] = '9';
--k;
}
if (!ch[i] && k > 1) {
c[i] = c[n - i - 1] = '9';
k -= 2;
}
}
}
if (n % 2 == 1 && k > 0) {
c[n/2] = '9';
}
System.out.println(new String(c));
}
}
// public static void main(String[] args) throws IOException {
//    BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
//
//  String[] nk = scanner.nextLine().split(" ");

//   int n = Integer.parseInt(nk[0]);
// int k = Integer.parseInt(nk[1]);

// String s = scanner.nextLine();

// String result = highestValuePalindrome(s, n, k);

//bufferedWriter.write(result);
// bufferedWriter.newLine();

// bufferedWriter.close();

//scanner.close();
// }
//}


Approach 3.

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;

public class Solution {

private static String largestPalindrome(String number, int k) {
char[] chars = number.toCharArray();
int minChange = 0;
for (int i = 0, j = chars.length - 1; i < j; i++, j--) {
if (chars[i] != chars[j]) {
minChange++;
}
}
if (minChange > k) {
return "-1";
}
int changeBoth = k - minChange;
int i = 0;
int j = chars.length - 1;
for (; i <= j; i++, j--) {
if (chars[i] != chars[j]) {
char maxChar = (char) Math.max(chars[i], chars[j]);
if (maxChar != '9' && changeBoth - 1 >= 0) {
chars[i] = '9';
chars[j] = '9';
changeBoth--;
} else {
chars[i] = maxChar;
chars[j] = maxChar;
minChange--;
}
} else {
char maxChar = (char) Math.max(chars[i], chars[j]);
if (maxChar != '9' && changeBoth - 2 >= 0) {
chars[i] = '9';
chars[j] = '9';
changeBoth -= 2;
}
}
}
if (changeBoth != 0 && i - 1 == j + 1) {
chars[i - 1] = '9';
}
String palindrome = new String(chars);
return palindrome;
}

public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int k = in.nextInt();
String number = in.next();
System.out.println(largestPalindrome(number, k));
}
}


### Solution in python3

Approach 1.

#!/bin/python3

import math
import os
import random
import re
import sys

# Complete the highestValuePalindrome function below.
def highestValuePalindrome(s, n, k):
s=list(s)
if n<=k:
return '9'*n
mink=[0]*(n//2+1)
for i in range(n//2-1,-1,-1):
if s[i]!=s[n-1-i]:
mink[i]=mink[i+1]+1
else:
mink[i]=mink[i+1]
if mink[0]>k:
return '-1'
i=0
while i<n//2 and k>mink[i]:
if s[i]=='9':
if s[n-1-i]!='9':
s[n-1-i]='9'
k-=1
elif s[n-1-i]=='9':
s[i]='9'
k-=1
elif k-2>=mink[i+1]:
s[i]=s[n-1-i]='9'
k-=2
else:
if s[i]!=s[n-1-i]:
s[i]=s[n-1-i]=max(s[n-1-i],s[i])
k-=1
i+=1
if i<n//2:
for j in range(i,n//2):
if s[j]>s[n-1-j]:
s[n-1-j]=s[j]
else:
s[j]=s[n-1-j]
elif n%2:
if k>0:
s[n//2]='9'
return ''.join(s)

if __name__ == '__main__':

nk = input().split()

n = int(nk[0])

k = int(nk[1])

s = input()

print(highestValuePalindrome(s, n, k))



Approach 2.

#!/bin/python3

import math
import os
import random
import re
import sys

# Complete the highestValuePalindrome function below.
def highestValuePalindrome(s, n, k):
j=0
v=n-1
c=0
s=[int(v) for v in s]
a=[0]*n
while j<n//2:
if s[j]!=s[v]:
c=c+1
s[j]=max(s[j],s[v])
s[v]=s[j]
a[j]=1
j=j+1
v=v-1
if c>k:
return '-1'
if c<k:
m=k-c
l=n//2
for j in range(l):
if a[j]==1:
if s[j]!=9:
m=m-1
s[j]=9
elif a[j]==0 and m>=2:
if s[j]!=9:
m=m-2
s[j]=9
if m==0:
break
print(s,a)
if n%2!=0:
if m>0:
s[n//2]=9
s=s[:l+1]+s[:l][::-1]
else:
s=s[:l]+s[:l][::-1]
print(s)
return "".join(map(str,s))

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()


Approach 3.

#!/bin/python3

import math
import os
import random
import re
import sys

# Complete the highestValuePalindrome function below.
def highestValuePalindrome(s, n, k):
s=list(s)
if n<=k:
return '9'*n
mink=[0]*(n//2+1)
for i in range(n//2-1,-1,-1):
if s[i]!=s[n-1-i]:
mink[i]=mink[i+1]+1
else:
mink[i]=mink[i+1]
if mink[0]>k:
return '-1'
i=0
while i<n//2 and k>mink[i]:
if s[i]=='9':
if s[n-1-i]!='9':
s[n-1-i]='9'
k-=1
elif s[n-1-i]=='9':
s[i]='9'
k-=1
elif k-2>=mink[i+1]:
s[i]=s[n-1-i]='9'
k-=2
else:
if s[i]!=s[n-1-i]:
s[i]=s[n-1-i]=max(s[n-1-i],s[i])
k-=1
i+=1
if i<n//2:
for j in range(i,n//2):
if s[j]>s[n-1-j]:
s[n-1-j]=s[j]
else:
s[j]=s[n-1-j]
elif n%2:
if k>0:
s[n//2]='9'
return ''.join(s)

s='12321'
n=5
k=1
ans= highestValuePalindrome(s, n, k)

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()


### Solution in cpp

Approach 1.

#include <iostream>
#include <string>

using namespace std;

int main (void) {

int n, k;
int i = 0;
string num;

cin >> n >> k >> num;

if (k >= n) {
cout << string(n, '9') << '\n';
} else {
int changes = 0;
for (i = 0; i < n/2; i++) {
if (num[i] != num[n-1-i])
changes++;
}

if (changes > k) {
cout << "-1\n";
} else {
for (i = 0; i < n/2; i++) {
if (num[i] == '9') {
if (num[n-1-i] != '9') {
num[n-1-i] = '9';
k--;
changes--;
}
} else {
if (num[i] == num[n-1-i]) {
if (k - changes >= 2) {
num[i] = '9';
num[n-1-i] = '9';
k -= 2;
}
} else {
if (num[n-1-i] == '9') {
num[i] = '9';
k--;
changes--;
} else if (k - changes >= 1) {
num[i] = '9';
num[n-1-i] = '9';
changes--;
k -= 2;
} else {
char max = num[i] > num[n-1-i] ? num[i] : num[n-1-i];
num[i] = max;
num[n-1-i] = max;
changes--;
k--;
}
}
}
}

if (k > 0 && n % 2)
num[n/2] = '9';

cout << num << '\n';
}
}

return 0;
}

Approach 2.

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <bitset>
#include <cstdio>
#include <limits>
#include <vector>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <fstream>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>

using namespace std;

int main(){
int n;
int k;
cin >> n >> k;
string s;
cin >> s;
int count = 0;
for (int i = 0; i < n/2; i++){
if (s[i] != s[n-1-i])
count++;
}
if (count > k){
cout << -1;
} else {
k -= count;
for (int i = 0; i < n/2; i++){
if (s[i] != s[n-1-i]){
if (k && max(s[i],s[n-1-i]) != '9') {
s[n-1-i] = s[i] = '9';
k--;
} else
s[n-1-i] = s[i] = max(s[i],s[n-1-i]);
} else if (k > 1 && s[i] != '9') {
s[n-1-i] = s[i] = '9';
k--; k--;
}
}
if (n % 2 == 1 && k){
s[(n-1)/2] = '9';
}
cout << s;
}
return 0;
}


Approach 3.

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <bitset>
#include <cstdio>
#include <limits>
#include <vector>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <fstream>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>

using namespace std;

int main(){
int n, k, c = 0;
string s;
cin >> n >> k >> s;

// counting minumum operations (c) needed to have a palindrome
for(int i = 0; i < (n+1)/2; i++)
c += s[i] != s[n-1-i];

if(c > k) s = "-1"; // if c > k it can't be done, so print -1
else for(int i = 0; i < (n+1)/2; i++) // else enter main loop
if(k - c > 1 && s[i] == s[n-i-1] && s[i] != '9'){ // case x---x
s[i] = s[n-1-i] = '9';
k -= 2;
} else if(s[i] != s[n-i-1]) // case x---y or y---x
if(k - c > 0){ // k surplus
s[i] == '9' || s[n-i-1] == '9' ? k-- : k -= 2;
s[i] = s[n-i-1] = '9';
c--;
} else { // no k surplus
s[i] = s[n-i-1] = max(s[i], s[n-i-1]);
k--;
}

// finally, fix middle value if necessary
if(k > 0 && n % 2)
s[n/2] = '9';

cout << s;
return 0;
}