Highest Value Palindrome
A series of technical programming questions I’ve dabbled with. This one comes from HackerRank.
Problem
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 0's left of all higher digits in your tests. For example0110is valid, 0011is 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 constraints.
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 FormatConstraints
0 <= n <= 10⁵
0 <= k <= 10⁵Example:
Input:
4 1
3943Output:
3993Further test cases:
s, n, k
("3943", 4, 1); //3993
("092282", 6, 3); //992299
("0011", 4, 1); //-1
("10011", 5, 1); //11011
("10011", 5, 3); //91019
("1111911", 7, 4); //9199919
("329", 3, 2); //999
("932239", 6, 2); //992299
("11119111", 8, 4); //91199119
("11117111", 8, 3); //91177119
("11117111", 8, 3); //91177119
("9711319", 7, 4); //9991999
("1111111", 7, 4); //9911199
("128392759430124", 15, 8); //929394959493929Solution
The first thing to consider is the properties of a palindrome. A palindrome is any representation of text; letters, numbers or a combination of both, that when read forwards or backwards, produces the same string. Writing a function to determine if a string is a palindrome would definitely help us understand this problem a little more.
A palindrome has properties such that if read forwards or backwards yields the same string. Given this, it can be asserted that with a function, if we compare the first and last position of a string, they should be the same. Then the second and second to last, and so forth. For some array, a, of size, n, from x to n-1,
x , x+1, x+2….m = n-n, … , n-3, n-2, n-1 where m = n
Given this, we can write
static boolean isPalindrome(String s){
int i = 0;
int j = s.length()-1;
while(j > i){
if (s.charAt(i) == s.charAt(j)){
i++; j--;
} else {
return false;
}
}
return true;
}This also handles the cases for odd and even length.
Given the properties listed above, the string, s, will have a number of difference across its indices. We need to determine the number of differences that are present in the string, e.g., for the string 3943, there is one difference, the middle values 9 and 4. If the number of differences exceeds the number of available changes, k, then the string cannot be fixed, and we return -1.
This is one of our first edge cases. When writing functions/methods, we should always consider what conditions will render our algorithm nonfunctional and what then should be the return value.
If we follow the same pattern of checking if the string is a palindrome, we need to compare the end indices.
We now have two considerations:
What do we do if the indices are equal?
What do we do if the indices are not equal?
Equal
If the indices are equal, for example in the case of 3943, indices 0 and 3 are equal. we need to check if we have any available changes remaining. If we have more than k=2 changes left, we can change these values to the maximum value, 9. Remember, we are trying to find the highest value palindrome possible. Also, we need to ensure that subtracting the 2 changes needed to switch the values to 9 does not leave the us with less changes than differences remaining.
This is important because if we waste the changes on two already equal indices, then other unequal indices lose the possibility of change.
We also do not want to waste applying a change if the value of the index is already 9.
If we meet these conditions, we change the index values to 9, and subtract 2 from k. We do not subtract from the differences variable, as there was no difference here.
Not Equal
If the values are not equal, then we can of course change them if we have changes, k, available.
Case 1:
If we have more than 2 changes available and using these changes will not result in available changes dropping below differences-1, then apply change. We decremented the difference because we have just resolved a difference.
Applying the change involves swapping the value for 9, if the value is not already 9.
Case 2:
If we do not have more than 2 changes available, then we swap the index with the lowest value out with the higher one. Then we decrement the changes available.
Final Consideration
Remember, a string can have an odd length, if that is the case, the indices converge at the middle. With a palindrome, this is fine as the middle value can be anything. However, we are trying to create the highest value palindrome. So if we have changes remaining, we use this and swap the middle value for 9.
Special Note: You can iterate through the string using either a while loop with lo and hi variables, checking for their convergence, or you can use a for loop, limiting it a n/2 (we only need to iterate half the length).
Algorithm
static String highestValuePalindrome(String s, int n, int k) {
int lo = 0;
int hi = n-1;;
char[] string = s.toCharArray();
int diff = 0;
for(int i=0, j=n-1; i<n/2; i++, j--){
if (string[i] != string[j]){
diff++;
}
}
if (diff > k){
return "-1";
}
while(hi >= lo){
if (k <= 0){
break;
}
if (string[lo] == string[hi]){
if (k > 1 && (k-2) >= diff && string[lo] != '9'){
string[lo] = '9';
string[hi] = '9';
k-=2;
}
}
else {
if (k > 1 && (k-2) >= diff-1){
if (string[lo] != '9'){
string[lo] = '9';
k--;
}
if (string[hi] != '9'){
string[hi] = '9';
k--;
}
} else {
if (string[lo] > string[hi]){
string[hi] = string[lo];
} else {
string[lo] = string[hi];
}
k--;
}
diff--;
}
if (lo == hi && k > 0){
string[lo] = '9';
k--;
}
lo++;
hi--;
}
s = String.valueOf(string);
return isPalindrome(s) ? s : "-1";
}