Make largest palindrome by changing at most K-digits
Given a string containing all digits, we need to convert this string to a palindrome by changing at most K digits. If many solutions are possible then print lexicographically largest one.
Examples:
Input : str = “43435”
k = 3
Output : "93939"
Explanation:
Lexicographically largest palindrome
after 3 changes is "93939"
Input : str = “43435”
k = 1
Output : “53435”
Explanation:
Lexicographically largest palindrome
after 3 changes is “53435”
Input : str = “12345”
k = 1
Output : "Not Possible"
Explanation:
It is not possible to make str palindrome
after 1 change.
Approach:
- Solve this problem using two pointers method. We start from left and right and if both digits are not equal then we replace the smaller value with larger value and decrease k by 1. S
- top when the left and right pointers cross each other, after they stop if value of k is negative, then it is not possible to make string palindrome using k changes. If k is positive, then we can further maximize the string by looping once again in the same manner from left and right and converting both the digits to 9 and decreasing k by 2.
- If k value remains to 1 and string length is odd then we make the middle character as 9 to maximize whole value.
Below is the implementation of above approach:
C++
// C++ program to get largest palindrome changing // atmost K digits #include <bits/stdc++.h> using namespace std; // Returns maximum possible // palindrome using k changes string maximumPalinUsingKChanges(string str, int k) { string palin = str; // Initialize l and r by leftmost and // rightmost ends int l = 0; int r = str.length() - 1; // first try to make string palindrome while (l < r) { // Replace left and right character by // maximum of both if (str[l] != str[r]) { palin[l] = palin[r] = max(str[l], str[r]); k--; } l++; r--; } // If k is negative then we can't make // string palindrome if (k < 0) return "Not possible" ; l = 0; r = str.length() - 1; while (l <= r) { // At mid character, if K>0 then change // it to 9 if (l == r) { if (k > 0) palin[l] = '9' ; } // If character at lth (same as rth) is // less than 9 if (palin[l] < '9' ) { /* If none of them is changed in the previous loop then subtract 2 from K and convert both to 9 */ if (k >= 2 && palin[l] == str[l] && palin[r] == str[r]) { k -= 2; palin[l] = palin[r] = '9' ; } /* If one of them is changed in the previous loop then subtract 1 from K (1 more is subtracted already) and make them 9 */ else if (k >= 1 && (palin[l] != str[l] || palin[r] != str[r])) { k--; palin[l] = palin[r] = '9' ; } } l++; r--; } return palin; } // Driver code to test above methods int main() { string str = "43435" ; int k = 3; cout << maximumPalinUsingKChanges(str, k); return 0; } |
Java
// Java program to get largest palindrome changing // atmost K digits import java.text.ParseException; class GFG { // Returns maximum possible // palindrome using k changes static String maximumPalinUsingKChanges(String str, int k) { char palin[] = str.toCharArray(); String ans = "" ; // Initialize l and r by leftmost and // rightmost ends int l = 0 ; int r = str.length() - 1 ; // First try to make String palindrome while (l < r) { // Replace left and right character by // maximum of both if (str.charAt(l) != str.charAt(r)) { palin[l] = palin[r] = ( char )Math.max( str.charAt(l), str.charAt(r)); k--; } l++; r--; } // If k is negative then we can't make // String palindrome if (k < 0 ) { return "Not possible" ; } l = 0 ; r = str.length() - 1 ; while (l <= r) { // At mid character, if K>0 then change // it to 9 if (l == r) { if (k > 0 ) { palin[l] = '9' ; } } // If character at lth (same as rth) is // less than 9 if (palin[l] < '9' ) { /* If none of them is changed in the previous loop then subtract 2 from K and convert both to 9 */ if (k >= 2 && palin[l] == str.charAt(l) && palin[r] == str.charAt(r)) { k -= 2 ; palin[l] = palin[r] = '9' ; } /* If one of them is changed in the previous loop then subtract 1 from K (1 more is subtracted already) and make them 9 */ else if (k >= 1 && (palin[l] != str.charAt(l) || palin[r] != str.charAt(r))) { k--; palin[l] = palin[r] = '9' ; } } l++; r--; } for ( int i = 0 ; i < palin.length; i++) ans += palin[i]; return ans; } // Driver code to test above methods public static void main(String[] args) throws ParseException { String str = "43435" ; int k = 3 ; System.out.println( maximumPalinUsingKChanges(str, k)); } } // This code is contributed by 29ajaykumar |
Python
# Python3 program to get largest palindrome changing # atmost K digits # Returns maximum possible # palindrome using k changes def maximumPalinUsingKChanges(strr, k): palin = strr[::] # Initialize l and r by leftmost and # rightmost ends l = 0 r = len (strr) - 1 # first try to make palindrome while (l < = r): # Replace left and right character by # maximum of both if (strr[l] ! = strr[r]): palin[l] = palin[r] = max (strr[l], strr[r]) # print(strr[l],strr[r]) k - = 1 l + = 1 r - = 1 # If k is negative then we can't make # palindrome if (k < 0 ): return "Not possible" l = 0 r = len (strr) - 1 while (l < = r): # At mid character, if K>0 then change # it to 9 if (l = = r): if (k > 0 ): palin[l] = '9' # If character at lth (same as rth) is # less than 9 if (palin[l] < '9' ): # If none of them is changed in the # previous loop then subtract 2 from K # and convert both to 9 if (k > = 2 and palin[l] = = strr[l] and palin[r] = = strr[r]): k - = 2 palin[l] = palin[r] = '9' # If one of them is changed in the previous # loop then subtract 1 from K (1 more is # subtracted already) and make them 9 elif (k > = 1 and (palin[l] ! = strr[l] or palin[r] ! = strr[r])): k - = 1 palin[l] = palin[r] = '9' l + = 1 r - = 1 return palin # Driver code st = "43435" strr = [i for i in st] k = 3 a = maximumPalinUsingKChanges(strr, k) print ("".join(a)) # This code is contributed by mohit kumar 29 |
C#
// C# program to get largest palindrome changing // atmost K digits using System; public class GFG { // Returns maximum possible // palindrome using k changes static String maximumPalinUsingKChanges(String str, int k) { char [] palin = str.ToCharArray(); String ans = "" ; // Initialize l and r by leftmost and // rightmost ends int l = 0; int r = str.Length - 1; // First try to make String palindrome while (l < r) { // Replace left and right character by // maximum of both if (str[l] != str[r]) { palin[l] = palin[r] = ( char )Math.Max(str[l], str[r]); k--; } l++; r--; } // If k is negative then we can't make // String palindrome if (k < 0) { return "Not possible" ; } l = 0; r = str.Length - 1; while (l <= r) { // At mid character, if K>0 then change // it to 9 if (l == r) { if (k > 0) { palin[l] = '9' ; } } // If character at lth (same as rth) is // less than 9 if (palin[l] < '9' ) { /* If none of them is changed in the previous loop then subtract 2 from K and convert both to 9 */ if (k >= 2 && palin[l] == str[l] && palin[r] == str[r]) { k -= 2; palin[l] = palin[r] = '9' ; } /* If one of them is changed in the previous loop then subtract 1 from K (1 more is subtracted already) and make them 9 */ else if (k >= 1 && (palin[l] != str[l] || palin[r] != str[r])) { k--; palin[l] = palin[r] = '9' ; } } l++; r--; } for ( int i = 0; i < palin.Length; i++) ans += palin[i]; return ans; } // Driver code to test above methods public static void Main() { String str = "43435" ; int k = 3; Console.Write(maximumPalinUsingKChanges(str, k)); } } // This code is contributed by Rajput-Ji |
Javascript
<script> // Javascript program to get largest palindrome changing // atmost K digits // Returns maximum possible // palindrome using k changes function maximumPalinUsingKChanges(str,k) { let palin = str.split( "" ); let ans = "" ; // Initialize l and r by leftmost and // rightmost ends let l = 0; let r = str.length - 1; // First try to make String palindrome while (l < r) { // Replace left and right character by // maximum of both if (str[l] != str[r]) { palin[l] = palin[r] = String.fromCharCode(Math.max( str.charAt(l), str.charAt(r))); k--; } l++; r--; } // If k is negative then we can't make // String palindrome if (k < 0) { return "Not possible" ; } l = 0; r = str.length - 1; while (l <= r) { // At mid character, if K>0 then change // it to 9 if (l == r) { if (k > 0) { palin[l] = '9 '; } } // If character at lth (same as rth) is // less than 9 if (palin[l] < ' 9 ') { /* If none of them is changed in the previous loop then subtract 2 from K and convert both to 9 */ if (k >= 2 && palin[l] == str[l] && palin[r] == str[r]) { k -= 2; palin[l] = palin[r] = ' 9 '; } /* If one of them is changed in the previous loop then subtract 1 from K (1 more is subtracted already) and make them 9 */ else if (k >= 1 && (palin[l] != str[l] || palin[r] != str[r])) { k--; palin[l] = palin[r] = ' 9'; } } l++; r--; } for (let i = 0; i < palin.length; i++) ans += palin[i]; return ans; } // Driver code to test above methods let str = "43435" ; let k = 3; document.write(maximumPalinUsingKChanges(str, k)); // This code is contributed by unknown2108 </script> |
93939
Time complexity: O(n)
Auxiliary Space: O(n) because it is using extra space for creating array and string
Approach 2: Using Greedy Algorithm
In this approach, we start by comparing the digits on the opposite ends of the given string. If they are equal, we move towards the center of the string. If they are not equal, we replace the smaller digit with the larger one to make the string a palindrome. We count the number of such replacements and stop when the number of replacements exceeds K or the string becomes a palindrome. If the number of replacements is less than K, we continue replacing digits with the largest ones until we reach the center of the string.
Here is the C++ code for this approach:
C++
#include <iostream> #include <string> using namespace std; string makePalindrome(string s, int k) { int n = s.length(); int replacements = 0; for ( int i = 0, j = n - 1; i < j; i++, j--) { if (s[i] != s[j]) { if (s[i] > s[j]) { s[j] = s[i]; } else { s[i] = s[j]; } replacements++; if (replacements > k) { return "-1" ; } } } for ( int i = 0, j = n - 1; i <= j; i++, j--) { if (i == j && replacements < k) { s[i] = '9' ; } if (s[i] != '9' ) { if (replacements < k && (i == 0 || i == j)) { s[i] = s[j] = '9' ; replacements++; } else if (replacements <= k - 2) { s[i] = s[j] = '9' ; replacements += 2; } } } return s; } int main() { string s = "43435" ; int k=3; cout << makePalindrome(s, k) << endl; return 0; } |
Java
// Java code to make the largest palindrome import java.util.*; class Main { public static String makePalindrome(String s, int k) { int n = s.length(); int replacements = 0 ; char [] arr = s.toCharArray(); for ( int i = 0 , j = n - 1 ; i < j; i++, j--) { if (arr[i] != arr[j]) { if (arr[i] > arr[j]) { arr[j] = arr[i]; } else { arr[i] = arr[j]; } replacements++; if (replacements > k) { return "-1" ; } } } for ( int i = 0 , j = n - 1 ; i <= j; i++, j--) { if (i == j && replacements < k) { arr[i] = '9' ; } if (arr[i] != '9' ) { if (replacements < k && (i == 0 || i == j)) { arr[i] = arr[j] = '9' ; replacements++; } else if (replacements <= k - 2 ) { arr[i] = arr[j] = '9' ; replacements += 2 ; } } } return new String(arr); } public static void main(String[] args) { String s = "43435" ; int k= 3 ; System.out.println(makePalindrome(s, k)); } } |
Python3
# Python program for the above approach # Function to make the string palindromic # by atmost K operations def make_palindrome(s, k): n = len (s) replacements = 0 s = list (s) # Iterate over the range [0, N/2] for i in range (n / / 2 ): j = n - i - 1 if s[i] ! = s[j]: if s[i] > s[j]: s[j] = s[i] else : s[i] = s[j] replacements + = 1 # If replacement is not possible if replacements > k: return "-1" for i in range (n / / 2 ): j = n - i - 1 if s[i] ! = '9' : if replacements < k and (i = = 0 or i = = j): s[i] = s[j] = '9' replacements + = 1 elif replacements < = k - 2 : s[i] = s[j] = '9' replacements + = 2 if n % 2 ! = 0 and replacements < k: s[n / / 2 ] = '9' # Return the resultant string return "".join(s) # Driver Code S = "43435" K = 3 print (make_palindrome(S, K)) |
C#
using System; class GFG { // Function to create the largest palindrome with given // replacements public static string MakePalindrome( string s, int k) { // Initialization int n = s.Length; int replacements = 0; char [] arr = s.ToCharArray(); // Iterate from the start and end of the string for ( int i = 0, j = n - 1; i < j; i++, j--) { // Replace characters if needed if (arr[i] != arr[j]) { if (arr[i] > arr[j]) { arr[j] = arr[i]; } else { arr[i] = arr[j]; } replacements++; // Check if replacements exceed the limit if (replacements > k) { return "-1" ; } } } // Iterate to handle remaining replacements for ( int i = 0, j = n - 1; i <= j; i++, j--) { // Handle middle element if applicable if (i == j && replacements < k) { arr[i] = '9' ; } // Replace other elements with '9' if (arr[i] != '9' ) { if (replacements < k && (i == 0 || i == j)) { arr[i] = arr[j] = '9' ; replacements++; } else if (replacements <= k - 2) { arr[i] = arr[j] = '9' ; replacements += 2; } } } // Return the resulting palindrome return new string (arr); } // Main method to demonstrate the function public static void Main( string [] args) { // Sample input string s = "43435" ; int k = 3; // Output the result Console.WriteLine(MakePalindrome(s, k)); } } |
Javascript
// function to make largest palindrome function makePalindrome(s, k) { let n = s.length; let replacements = 0; // Make the string a palindrome by making minimal character replacements for (let i = 0, j = n - 1; i < j; i++, j--) { if (s[i] != s[j]) { if (s[i] > s[j]) { s = s.substring(0, j) + s[i] + s.substring(j + 1); } else { s = s.substring(0, i) + s[j] + s.substring(i + 1); } replacements++; if (replacements > k) { return "-1" ; } } } // Replace remaining characters with 9 for (let i = 0, j = n - 1; i <= j; i++, j--) { if (i == j && replacements < k) { s = s.substring(0, i) + "9" + s.substring(i + 1); } if (s[i] != "9" ) { if (replacements < k && (i == 0 || i == j)) { s = s.substring(0, i) + "9" + s.substring(i + 1); s = s.substring(0, j) + "9" + s.substring(j + 1); replacements++; } else if (replacements <= k - 2) { s = s.substring(0, i) + "9" + s.substring(i + 1); s = s.substring(0, j) + "9" + s.substring(j + 1); replacements += 2; } } } // return the maximum lenght palindrome return s; } // driver code to test above function let s = "43435" ; let k = 3; // function call console.log(makePalindrome(s, k)); |
93939
The time complexity of the first approach is O(N^2), where N is the length of the string, because we are using two nested loops to compare every pair of characters in the string.
The space complexity is O(N), because we are creating a new string of length N to store the modified palindrome.
Contact Us