Largest Palindrome by Changing at Most K-digits in Java

A palindrome number is a number that remains the same when its digits are reversed. In other words, it reads the same backward as forward. Here we have one string that contains all the digits, we have to convert this string to a palindrome by changing at most K digits. If multiple solutions are possible then print lexicographically the largest one.

Example 1

Input:

Str = ”123456”

K = 3

Output:

“654456”

Explanation:

The initial number is "123456" and the maximum number of digit changes allowed is 3. Then we modified the digits at positions 0, 1, and 5 to create the largest possible palindrome while staying within the limit of 3-digit changes. The resulting largest palindrome is "654456".

Approach: Using Two Pointer Approach

Here we are using two pointer approach so first we have to Convert the given number to a string. Then Create a character array from the string to allow modification of individual digits. Here we have to use two pointers, one will start from the left end of the array and the other will start from the right end of the array. Iterate through the array while the left pointer is less than or equal to the right pointer.

FileName: LargestPalindrome.java

public class LargestPalindrome {
 public static String findLargestPalindrome(String num, int k) {
 // Convert the given number to a character array
 char[] digits = num.toCharArray();
 int left = 0;
 int right = digits.length - 1;
 // Iterate through the array from both ends towards the middle
 while (left <= right) {
 // If the digits at the left and right pointers are not equal
 if (digits[left] != digits[right]) {
 // If no more digit changes are allowed, break the loop
 if (k <= 0) {
 break;
 }
 // Replace the digit at the left pointer with the maximum of the two digits
 digits[left] = digits[right] = (char) Math.max(digits[left], digits[right]);
 // Decrement the available digit changes
 k--;
 }
 // Move the left pointer to the right and the right pointer to the left
 left++;
 right--;
 }
 // Convert the character array back to a string and return it
 return String.valueOf(digits);
 }
 public static void main(String[] args) {
 String num = "123456";
 int k = 3;
 // Find the largest palindrome by changing at most k digits
 String largestPalindrome = findLargestPalindrome(num, k);
 System.out.println("Largest palindrome Number is: " + largestPalindrome);
 }
}

Output:

Largest palindrome Number is: 654456

Complexity:

The overall time complexity of this code is O(n), where n is the length of the input number. The space complexity is O(n) as well, considering the need to store the character array representation of the number. the code has a linear time complexity of O(n) and a linear space complexity of O(n).

Approach: Greedy Algorithm

In the greedy algorithm approach, when encountering a mismatch between digits at the left and right pointers, we greedily choose the larger digit to replace the smaller one. This ensures that we maximize the value of the resulting palindrome at each step.

FileName: LargestPalindrome.java

public class LargestPalindrome {
 public static String findLargestPalindrome(String num, int k) {
 // Convert the given number to a character array
 char[] digits = num.toCharArray();
 int left = 0;
 int right = digits.length - 1;
 // Iterate through the array from both ends towards the middle
 while (left <= right) {
 // If the digits at the left and right pointers are not equal
 if (digits[left] != digits[right]) {
 // Greedily replace the smaller digit with the larger digit
 if (digits[left] < digits[right]) {
 digits[left] = digits[right];
 } else {
 digits[right] = digits[left];
 }
 // Decrement the available digit changes
 k--;
 }
 // Move the left pointer to the right and the right pointer to the left
 left++;
 right--;
 }
 // Convert the character array back to a string and return it
 return String.valueOf(digits);
 }
 public static void main(String[] args) {
 String num = "123456";
 int k = 3;
 // Find the largest palindrome by changing at most k digits
 String largestPalindrome = findLargestPalindrome(num, k);
 System.out.println("Largest palindrome Number is: " + largestPalindrome);
 }
}

Output:

Largest palindrome Number is: 654456

Complexity:

The complexity of the greedy algorithm for finding the largest palindrome by changing at most k digits is as follows, the overall time complexity of this algorithm is O(n), where n is the length of the input number. The space complexity is O(n) as well, considering the need to store the character array representation of the number.