Dada la string numérica str , la tarea es encontrar las operaciones mínimas necesarias para hacer el palíndromo de strings . Una operación se define como:
- Seleccione un carácter y elimine cualquiera de sus ocurrencias .
- Para todas las operaciones, el número de caracteres únicos elegidos debe ser inferior a 2
Ejemplos :
Entrada : str = “11221”
Salida : 1
Explicación : seleccione ‘1’ y elimine cualquier carácter de los dos primeros caracteres de la string dada. Después de la operación, la string se convierte en “1221”, que es un palíndromo.Entrada : str = “1123211”
Salida : 0
Explicación : la string dada ya es un palíndromo.Entrada : str = “1332”
Salida : -1
Explicación : la string no se puede convertir en palíndromo después de seleccionar un solo carácter y eliminar las ocurrencias del carácter seleccionado únicamente.
Enfoque: Este problema se puede resolver con la ayuda del enfoque de dos puntos .
Siga los pasos a continuación para resolver el problema:
- Inicializa una respuesta variable como n que almacena nuestra respuesta final (n es la longitud de la string).
- Itere sobre ‘0’ a ‘9’ y llamémoslo currentCharacter.
- Inicialice toBeRemoved como 0 . Almacena la cantidad mínima de caracteres que se eliminarán del tipo de carácter actual de la string para convertirla en un palíndromo.
- Inicialice i y j como 0 y n – 1 respectivamente.
- Inicializar un posible como verdadero . Nos ayuda a determinar si es posible hacer el palíndromo de strings eliminando las ocurrencias del carácter c solamente.
- Ahora ejecute un ciclo while anidado hasta que i sea menor que j .
- Caso 1: str[i] es igual a str[j], significa que no estamos obligados a eliminar ningún carácter en el paso actual, por lo que podemos incrementar i y disminuir j.
- Caso 2: str[i] no es igual a str[j] pero str[i] es igual a currentCharacter. Incremente i = i + 1 y toBeRemoved = toBeRemoved + 1 ya que estamos eliminando este carácter.
- Caso 3: str[i] no es igual a str[j] pero str[j] es igual a currentCharacter. Incremente j = j – 1 y toBeRemoved = toBeRemoved + 1 ya que estamos eliminando este carácter
- Caso 4: str[i] no es igual a str[j]. Significa que no podemos hacer que nuestro palíndromo de strings elimine el carácter actual.
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 operations
void solve(string str)
{
// Length of the string
int n = str.length();
// answer variable for final answer
// initializing it with INF
int answer = n;
// Iterating over characters
// from '0' to '9' (string
// consist of those characters only)
for (char currentCharacter = '0';
currentCharacter <= '9';
currentCharacter++) {
// i and j variables to check corresponding
// characters from the start and the end
int i = 0, j = n - 1;
// toBeRemoved store the character of type
// currentCharacter to be removed
// to make the string palindrome
int toBeRemoved = 0;
bool possible = true;
while (i < j) {
// If corresponding currentCharacters are
// already same
if (str[i] == str[j]) {
i++, j--;
}
// If corresponding currentCharacters are
// not same and str[i] is equal to
// currentCharacter
// remove it and check for str[i + 1] and
// str[j] in the next iteration
else if (str[i] != str[j]
&& str[i] == currentCharacter) {
toBeRemoved++;
i++;
}
// If corresponding currentCharacters are
// not same and str[j] is equal to
// currentCharacter
// remove it and check for str[j - 1] and
// str[i] in the next iteration
else if (str[i] != str[j]
&& str[j] == currentCharacter) {
toBeRemoved++;
j--;
}
// Character of currentCharacter type
// can't be removed
// to make the str palindrome.
// Hence, we mark possible to false
// break out of the loop
else {
possible = false;
break;
}
}
// If it is possible to remove
// some occurrences of currentCharacters
// we will update our answer
if (possible)
// Take the minimum value out
// of answer and toBeRemoved
answer = min(answer, toBeRemoved);
}
// Print the final answer
if (answer == n)
cout << "-1";
else
cout << answer;
}
// Driver Code
int main()
{
// Given string
string str = "11221";
solve(str);
}
Java
// Java code for the above approach
import java.io.*;
class GFG
{
// Function to find the minimum operations
static void solve(String str)
{
// Length of the string
int n = str.length();
// answer variable for final answer
// initializing it with INF
int answer = n;
// Iterating over characters
// from '0' to '9' (string
// consist of those characters only)
for (char currentCharacter = '0';
currentCharacter <= '9';
currentCharacter++) {
// i and j variables to check corresponding
// characters from the start and the end
int i = 0, j = n - 1;
// toBeRemoved store the character of type
// currentCharacter to be removed
// to make the string palindrome
int toBeRemoved = 0;
boolean possible = true;
while (i < j) {
// If corresponding currentCharacters are
// already same
if (str.charAt(i) == str.charAt(j)) {
i++; j--;
}
// If corresponding currentCharacters are
// not same and str[i] is equal to
// currentCharacter
// remove it and check for str[i + 1] and
// str[j] in the next iteration
else if (str.charAt(i) != str.charAt(j)
&& str.charAt(i) == currentCharacter) {
toBeRemoved++;
i++;
}
// If corresponding currentCharacters are
// not same and str[j] is equal to
// currentCharacter
// remove it and check for str[j - 1] and
// str[i] in the next iteration
else if (str.charAt(i) != str.charAt(j)
&& str.charAt(j) == currentCharacter) {
toBeRemoved++;
j--;
}
// Character of currentCharacter type
// can't be removed
// to make the str palindrome.
// Hence, we mark possible to false
// break out of the loop
else {
possible = false;
break;
}
}
// If it is possible to remove
// some occurrences of currentCharacters
// we will update our answer
if (possible)
// Take the minimum value out
// of answer and toBeRemoved
answer = Math.min(answer, toBeRemoved);
}
// Print the final answer
if (answer == n)
System.out.println("-1");
else
System.out.println(answer);
}
// Driver Code
public static void main (String[] args)
{
// Given string
String str = "11221";
solve(str);
}
}
// This code is contributed by lokeshpotta20.
Python3
# Python program for the above approach
# Function to find the minimum operations
def solve(str):
# Length of the string
n = len(str)
# answer variable for final answer
# initializing it with INF
answer = n;
currentCharacter = '0'
# Iterating over characters
# from '0' to '9' (string
# consist of those characters only)
while(currentCharacter <= '9'):
# i and j variables to check corresponding
# characters from the start and the end
i = 0
j = n - 1
# toBeRemoved store the character of type
# currentCharacter to be removed
# to make the string palindrome
toBeRemoved = 0
possible = True
while (i < j):
# If corresponding currentCharacters are
# already same
if (str[i] == str[j]):
i += 1
j -= 1
# If corresponding currentCharacters are
# not same and str[i] is equal to
# currentCharacter
# remove it and check for str[i + 1] and
# str[j] in the next iteration
elif (str[i] != str[j] and str[i] == currentCharacter):
toBeRemoved += 1
i += 1
# If corresponding currentCharacters are
# not same and str[j] is equal to
# currentCharacter
# remove it and check for str[j - 1] and
# str[i] in the next iteration
elif (str[i] != str[j] and str[j] == currentCharacter):
toBeRemoved += 1
j -= 1
# Character of currentCharacter type
# can't be removed
# to make the str palindrome.
# Hence, we mark possible to false
# break out of the loop
else:
possible = False;
break;
currentCharacter = f"{int(currentCharacter) + 1}"
# If it is possible to remove
# some occurrences of currentCharacters
# we will update our answer
if (possible):
# Take the minimum value out
# of answer and toBeRemoved
answer = min(answer, toBeRemoved);
# Print the final answer
if (answer == n):
print("-1");
else:
print(answer);
# Driver Code
# Given string
str = "11221";
solve(str);
# This code is contributed by Saurabh Jaiswal
C#
// C# program for above approach
using System;
class GFG
{
// Function to find the minimum operations
static void solve(string str)
{
// Length of the string
int n = str.Length;
// answer variable for final answer
// initializing it with INF
int answer = n;
// Iterating over characters
// from '0' to '9' (string
// consist of those characters only)
for (char currentCharacter = '0';
currentCharacter <= '9';
currentCharacter++) {
// i and j variables to check corresponding
// characters from the start and the end
int i = 0, j = n - 1;
// toBeRemoved store the character of type
// currentCharacter to be removed
// to make the string palindrome
int toBeRemoved = 0;
bool possible = true;
while (i < j) {
// If corresponding currentCharacters are
// already same
if (str[i] == str[j]) {
i++;
j--;
}
// If corresponding currentCharacters are
// not same and str[i] is equal to
// currentCharacter
// remove it and check for str[i + 1] and
// str[j] in the next iteration
else if (str[i] != str[j]
&& str[i] == currentCharacter) {
toBeRemoved++;
i++;
}
// If corresponding currentCharacters are
// not same and str[j] is equal to
// currentCharacter
// remove it and check for str[j - 1] and
// str[i] in the next iteration
else if (str[i] != str[j]
&& str[j] == currentCharacter) {
toBeRemoved++;
j--;
}
// Character of currentCharacter type
// can't be removed
// to make the str palindrome.
// Hence, we mark possible to false
// break out of the loop
else {
possible = false;
break;
}
}
// If it is possible to remove
// some occurrences of currentCharacters
// we will update our answer
if (possible)
// Take the minimum value out
// of answer and toBeRemoved
answer = Math.Min(answer, toBeRemoved);
}
// Print the final answer
if (answer == n)
Console.Write("-1");
else
Console.Write(answer);
}
// Driver Code
public static void Main()
{
// Given string
string str = "11221";
solve(str);
}
}
// This code is contributed by Samim Hossain Mondal.
Javascript
<script>
// Javascript program for the above approach
// Function to find the minimum operations
function solve(str)
{
// Length of the string
let n = str.length;
// answer variable for final answer
// initializing it with INF
let answer = n;
// Iterating over characters
// from '0' to '9' (string
// consist of those characters only)
for (let currentCharacter = '0';
currentCharacter <= '9';
currentCharacter++) {
// i and j variables to check corresponding
// characters from the start and the end
let i = 0, j = n - 1;
// toBeRemoved store the character of type
// currentCharacter to be removed
// to make the string palindrome
let toBeRemoved = 0;
let possible = true;
while (i < j) {
// If corresponding currentCharacters are
// already same
if (str[i] == str[j]) {
i++;
j--;
}
// If corresponding currentCharacters are
// not same and str[i] is equal to
// currentCharacter
// remove it and check for str[i + 1] and
// str[j] in the next iteration
else if (str[i] != str[j]
&& str[i] == currentCharacter) {
toBeRemoved++;
i++;
}
// If corresponding currentCharacters are
// not same and str[j] is equal to
// currentCharacter
// remove it and check for str[j - 1] and
// str[i] in the next iteration
else if (str[i] != str[j]
&& str[j] == currentCharacter) {
toBeRemoved++;
j--;
}
// Character of currentCharacter type
// can't be removed
// to make the str palindrome.
// Hence, we mark possible to false
// break out of the loop
else {
possible = false;
break;
}
}
// If it is possible to remove
// some occurrences of currentCharacters
// we will update our answer
if (possible)
// Take the minimum value out
// of answer and toBeRemoved
answer = Math.min(answer, toBeRemoved);
}
// Print the final answer
if (answer == n)
document.write("-1");
else
document.write(answer);
}
// Driver Code
// Given string
let str = "11221";
solve(str);
// This code is contributed by Samim Hossain Mondal.
</script>
Producción
1
Complejidad de tiempo : O(10 * n) = O(n) donde n es la longitud de la string str.
Espacio Auxiliar : O(1)