Dada una string S de longitud N que consta de letras minúsculas, la tarea es encontrar el número mínimo de operaciones para convertir la string dada en un palíndromo . En una sola operación, elija cualquier carácter y reemplácelo por su alfabeto siguiente o anterior.
Nota: Los alfabetos son cíclicos, es decir, si z aumenta, se convierte en a y si a disminuye, se convierte en z .
Ejemplos:
Entrada: S = “arcehesmz”
Salida: 16
Explicación:
La posible transformación que dada la cuenta mínima de operación es:
- Disminuya el primer carácter ‘a’ en 1 para obtener ‘z’ . Recuento de operaciones = 1
- Disminuya el tercer carácter ‘c’ en 10 para obtener ‘s’ . Cuenta de operaciones = 1 + 10 = 11
- Aumente el octavo carácter ‘m’ en 5 para obtener ‘r’ . Cuenta de operaciones = 11 + 5 = 16.
Por lo tanto, el recuento total de operaciones es 16.
Entrada: S = “abccdb”
Salida: 3
Explicación:
La posible transformación que dada la cuenta mínima de operación es:
- Aumente el primer carácter ‘a’ en 1 para obtener ‘b’ . Recuento de operaciones = 1
- Aumente el segundo carácter ‘b’ en 2 para obtener ‘d’ . Cuenta de operaciones = 1 + 2 = 3.
Enfoque ingenuo: el enfoque más simple es generar todas las strings posibles de longitud N . Luego verifique cada string, si es un palíndromo . Si se encuentra que alguna string es palindrómica, encuentre el costo de operación requerido para convertir la string dada en esa string. Repita los pasos anteriores para todas las strings generadas e imprima el costo mínimo calculado entre todos los costos.
Complejidad de Tiempo: O(26 N )
Espacio Auxiliar: O(N)
Enfoque eficiente: para optimizar el enfoque anterior, la idea es atravesar la string dada y encontrar el cambio para cada posición de forma independiente. Siga los pasos a continuación para resolver el problema:
- Atraviesa la string dada en el rango [0, (N/2) – 1] .
- Para cada carácter en el índice i , encuentre la diferencia absoluta entre los caracteres en los índices i y (N – i – 1) .
- Puede haber dos diferencias posibles, es decir, la diferencia cuando el carácter en i se incrementa al carácter en el índice (N – i – 1) y cuando se reduce en ese índice.
- Toma el mínimo de ambos y súmalo al resultado.
- Después de los pasos anteriores, imprima el costo mínimo calculado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the minimum number
// of operations required to convert
// th given string into palindrome
int minOperations(string s)
{
int len = s.length();
int result = 0;
// Iterate till half of the string
for (int i = 0; i < len / 2; i++) {
// Find the absolute difference
// between the characters
int D1 = max(s[i], s[len - 1 - i])
- min(s[i], s[len - 1 - i]);
int D2 = 26 - D1;
// Adding the minimum difference
// of the two result
result += min(D1, D2);
}
// Return the result
return result;
}
// Driver Code
int main()
{
// Given string
string s = "abccdb";
// Function Call
cout << minOperations(s);
return 0;
}
Java
// Java program for the above approach
class GFG{
// Function to find the minimum number
// of operations required to convert
// th given string into palindrome
public static int minOperations(String s)
{
int len = s.length();
int result = 0;
// Iterate till half of the string
for(int i = 0; i < len / 2; i++)
{
// Find the absolute difference
// between the characters
int D1 = Math.max(s.charAt(i),
s.charAt(len - 1 - i)) -
Math.min(s.charAt(i),
s.charAt(len - 1 - i));
int D2 = 26 - D1;
// Adding the minimum difference
// of the two result
result += Math.min(D1, D2);
}
// Return the result
return result;
}
// Driver code
public static void main(String[] args)
{
// Given string
String s = "abccdb";
// Function call
System.out.println(minOperations(s));
}
}
// This code is contributed by divyeshrabadiya07
Python3
# Python3 program for the above approach # Function to find the minimum number # of operations required to convert # th given string into palindrome def minOperations(s): length = len(s) result = 0 # Iterate till half of the string for i in range(length // 2): # Find the absolute difference # between the characters D1 = (ord(max(s[i], s[length - 1 - i])) - ord(min(s[i], s[length - 1 - i]))) D2 = 26 - D1 # Adding the minimum difference # of the two result result += min(D1, D2) # Return the result return result # Driver Code # Given string s = "abccdb" # Function call print(minOperations(s)) # This code is contributed by Shivam Singh
C#
// C# program for the above approach
using System;
class GFG{
// Function to find the minimum number
// of operations required to convert
// th given string into palindrome
public static int minOperations(String s)
{
int len = s.Length;
int result = 0;
// Iterate till half of the string
for(int i = 0; i < len / 2; i++)
{
// Find the absolute difference
// between the characters
int D1 = Math.Max(s[i],
s[len - 1 - i]) -
Math.Min(s[i],
s[len - 1 - i]);
int D2 = 26 - D1;
// Adding the minimum difference
// of the two result
result += Math.Min(D1, D2);
}
// Return the result
return result;
}
// Driver code
public static void Main(String[] args)
{
// Given string
String s = "abccdb";
// Function call
Console.WriteLine(minOperations(s));
}
}
// This code is contributed by Amit Katiyar
Javascript
<script>
// JavaScript program for the above approach
// Function to find the minimum number
// of operations required to convert
// th given string into palindrome
function minOperations(s)
{
var len = s.length;
var result = 0;
// Iterate till half of the string
for (var i = 0; i < len / 2; i++)
{
// Find the absolute difference
// between the characters
var D1 =
Math.max(s[i].charCodeAt(0), s[len - 1 - i].charCodeAt(0)) -
Math.min(s[i].charCodeAt(0), s[len - 1 - i].charCodeAt(0));
var D2 = 26 - D1;
// Adding the minimum difference
// of the two result
result += Math.min(D1, D2);
}
// Return the result
return result;
}
// Driver Code
// Given string
var s = "abccdb";
// Function Call
document.write(minOperations(s));
// This code is contributed by rdtank.
</script>
Producción:
3
Complejidad temporal: O(N)
Espacio auxiliar: O(N)