Dada una string S de longitud N y un número entero P que denota un puntero al P -ésimo índice de la string, la tarea es encontrar el costo mínimo para convertir la string en un palíndromo realizando las siguientes operaciones:
- El puntero P se puede mover del índice i al índice j y el costo requerido es |i – j| donde 0 ≤ yo < norte y 0 ≤ j < norte .
- El costo de cambiar el carácter en el índice Pth es 1 .
Ejemplos:
Entrada: S = “saad”, P = 1
Salida: 2
Explicación:
Inicialmente, el puntero está en el índice 1.
Paso 1: Mueva el puntero al índice 0. Por lo tanto, costo = 1 – 0 = 1.
Paso 2: Cambie el carácter s a d. Por lo tanto, costo = 1 + 1 = 2 y S = «papá».
Por lo tanto, el costo es 2.Entrada: S = “bajo”, P = 3
Salida: 3
Explicación:
Inicialmente, el puntero está en el índice 3.
Paso 1: Cambie el carácter en el índice P = 3 a b. Por lo tanto, costo = 1 y S = “basb”.
Paso 2: Mueva el puntero al índice 2. Por lo tanto, costo = 1 + 1 = 2.
Paso 3: Cambie el carácter en el índice P = 2 a a. Por lo tanto, costo = 3 y S = “baab”.
Por lo tanto, el costo es 3.
Enfoque: la idea es encontrar el primer y el último carácter que debe cambiarse en la primera mitad de la string cuando el puntero está en la primera mitad o invertir la string si el puntero está en la segunda mitad y ajustar el puntero en consecuencia. . Siga los pasos a continuación para resolver el problema:
- Si el puntero está en la segunda mitad, invierta la string y cambie el puntero a (N – 1 – P) .
- Ahora, encuentre la posición del carácter más lejano necesario para cambiar en el lado izquierdo y derecho en la primera mitad de la string. Sean l y r .
- Encuentre el costo total para cambiar los caracteres, es decir, el total de caracteres en la primera mitad tal que S[i] != s[N – i – 1] donde 0 < i < N/2 .
- La distancia mínima transversal para cambiar los caracteres es min(2*(P – l) + r – P, 2*(r – P) + P – l) .
- Imprime la respuesta como la suma del costo de cambiar los caracteres y la distancia mínima a recorrer.
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 cost to
// convert the string into a palindrome
int findMinCost(string str, int pos)
{
// Length of the string
int n = str.length();
// If iointer is in the second half
if (pos >= n / 2) {
// Reverse the string
reverse(str.begin(), str.end());
pos = n - pos - 1;
}
int left, right;
// Pointing to initial position
left = right = pos;
// Find the farthest index needed to
// change on left side
for (int i = pos; i >= 0; --i) {
if (str[i] != str[n - i - 1]) {
left = i;
}
}
// Find the farthest index needed to
// change on right side
for (int i = pos; i < n / 2; ++i) {
if (str[i] != str[n - i - 1]) {
right = i;
}
}
int ans = 0;
for (int i = left; i <= right; ++i) {
// Changing the variable to make
// string palindrome
if (str[i] != str[n - i - 1])
ans += 1;
}
// min distance to travel to make
// string palindrome
int dis = min((2 * (pos - left)
+ (right - pos)),
(2 * (right - pos)
+ (pos - left)));
// Total cost
ans = ans + dis;
// Return the minimum cost
return ans;
}
// Driver Code
int main()
{
// Given string S
string S = "bass";
// Given pointer P
int P = 3;
// Function Call
cout << findMinCost(S, P);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to find the minimum cost to
// convert the string into a palindrome
static int findMinCost(String str, int pos)
{
// Length of the string
int n = str.length();
StringBuilder input1 = new StringBuilder();
input1.append(str);
// If iointer is in the second half
if (pos >= n / 2)
{
// Reverse the string
input1 = input1.reverse();
pos = n - pos - 1;
}
int left, right;
// Pointing to initial position
left = right = pos;
// Find the farthest index needed to
// change on left side
for(int i = pos; i >= 0; --i)
{
if (input1.charAt(i) !=
input1.charAt(n - i - 1))
{
left = i;
}
}
// Find the farthest index needed to
// change on right side
for(int i = pos; i < n / 2; ++i)
{
if (input1.charAt(i) !=
input1.charAt(n - i - 1))
{
right = i;
}
}
int ans = 0;
for(int i = left; i <= right; ++i)
{
// Changing the variable to make
// string palindrome
if (input1.charAt(i) !=
input1.charAt(n - i - 1))
ans += 1;
}
// min distance to travel to make
// string palindrome
int dis = Math.min((2 * (pos - left) +
(right - pos)),
(2 * (right - pos) +
(pos - left)));
// Total cost
ans = ans + dis;
// Return the minimum cost
return ans;
}
// Driver Code
public static void main(String args[])
{
// Given string S
String S = "bass";
// Given pointer P
int P = 3;
// Function Call
System.out.println(findMinCost(S, P));
}
}
// This code is contributed by bgangwar59
Python3
# Python3 program for the above approach # Function to find the minimum cost to # convert the into a palindrome def findMinCost(strr, pos): # Length of the string n = len(strr) # If iointer is in the second half if (pos >= n / 2): # Reverse the string strr = strr[::-1] pos = n - pos - 1 left, right = pos, pos # Pointing to initial position # left = right = pos # Find the farthest index needed # to change on left side for i in range(pos, -1, -1): if (strr[i] != strr[n - i - 1]): left = i # Find the farthest index needed # to change on right side for i in range(pos, n // 2): if (strr[i] != strr[n - i - 1]): right = i ans = 0 for i in range(left, right + 1): # Changing the variable to make # palindrome if (strr[i] != strr[n - i - 1]): ans += 1 # min distance to travel to make # palindrome dis = (min((2 * (pos - left) + (right - pos)), (2 * (right - pos) + (pos - left)))) # Total cost ans = ans + dis # Return the minimum cost return ans # Driver Code if __name__ == '__main__': # Given S S = "bass" # Given pointer P P = 3 # Function Call print(findMinCost(S, P)) # This code is contributed by mohit kumar 29
C#
// C# program for the
// above approach
using System;
class GFG{
// Function to find the minimum
// cost to convert the string
// into a palindrome
static int findMinCost(string str,
int pos)
{
// Length of the string
int n = str.Length;
char[] charArray =
str.ToCharArray();
// If iointer is in the
// second half
if (pos >= n / 2)
{
// Reverse the string
Array.Reverse(charArray);
pos = n - pos - 1;
}
int left, right;
// Pointing to initial position
left = right = pos;
// Find the farthest index
// needed to change on
// left side
for(int i = pos; i >= 0; --i)
{
if (charArray[i] !=
charArray[n - i - 1])
{
left = i;
}
}
// Find the farthest index
// needed to change on right
// side
for(int i = pos; i < n / 2; ++i)
{
if (charArray[i] !=
charArray[n - i - 1])
{
right = i;
}
}
int ans = 0;
for(int i = left; i <= right; ++i)
{
// Changing the variable to make
// string palindrome
if (charArray[i]!=
charArray[n - i - 1])
ans += 1;
}
// min distance to travel to make
// string palindrome
int dis = Math.Min((2 * (pos - left) +
(right - pos)),
(2 * (right - pos) +
(pos - left)));
// Total cost
ans = ans + dis;
// Return the minimum cost
return ans;
}
// Driver Code
public static void Main()
{
// Given string S
string S = "bass";
// Given pointer P
int P = 3;
// Function Call
Console.Write(findMinCost(S, P));
}
}
// This code is contributed by Chitranayal
Javascript
<script>
// Javascript program for the above approach
// Function to find the minimum cost to
// convert the string into a palindrome
function findMinCost(str, pos)
{
// Length of the string
var n = str.length;
// If iointer is in the second half
if (pos >= n / 2)
{
// Reverse the string
str.split('').reverse().fill('');
pos = n - pos - 1;
}
var left, right;
// Pointing to initial position
left = right = pos;
// Find the farthest index needed to
// change on left side
for(var i = pos; i >= 0; --i)
{
if (str[i] != str[n - i - 1])
{
left = i;
}
}
// Find the farthest index needed to
// change on right side
for(var i = pos; i < n / 2; ++i)
{
if (str[i] != str[n - i - 1])
{
right = i;
}
}
var ans = 0;
for(var i = left; i <= right; ++i)
{
// Changing the variable to make
// string palindrome
if (str[i] != str[n - i - 1])
ans += 1;
}
// min distance to travel to make
// string palindrome
var dis = Math.min((2 * (pos - left) +
(right - pos)),
(2 * (right - pos) +
(pos - left)));
// Total cost
ans = ans + dis;
// Return the minimum cost
return ans;
}
// Driver Code
// Given string S
var S = "bass";
// Given pointer P
var P = 3;
// Function Call
document.write(findMinCost(S, P));
// This code is contributed by itsok
</script>
Producción
3
Complejidad temporal: O(N)
Espacio auxiliar: O(N)