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