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