Dada una string que contiene todos los dígitos, necesitamos convertir esta string en un palíndromo cambiando como máximo K dígitos. Si hay muchas soluciones posibles, imprima lexicográficamente la más grande.
Ejemplos:
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.
Acercarse:
- Resuelve este problema usando el método de dos punteros. Comenzamos de izquierda a derecha y si ambos dígitos no son iguales, reemplazamos el valor más pequeño con un valor más grande y disminuimos k en 1. S
- arriba cuando los punteros izquierdo y derecho se cruzan, después de que se detienen si el valor de k es negativo, entonces no es posible hacer un palíndromo de strings usando cambios de k. Si k es positivo, entonces podemos maximizar aún más la string haciendo un bucle una vez más de la misma manera de izquierda a derecha y convirtiendo ambos dígitos en 9 y disminuyendo k en 2.
- Si el valor de k permanece en 1 y la longitud de la string es impar, hacemos que el carácter del medio sea 9 para maximizar el valor total.
A continuación se muestra la implementación del enfoque anterior:
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
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
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
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>
Producción:
93939
Complejidad temporal: O(n)
Espacio Auxiliar: O(1)
Este artículo es una contribución de Utkarsh Trivedi . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA