Compruebe si la string dada se puede convertir en palíndromo eliminando solo un tipo de carácter | Conjunto-2

Es palíndromo igual cualquiera

Ejemplos:

Entrada: S = ““
Salida: Sí
Explicación:

Entrada: S = “madem”
Salida: No
Explicación: Dado que solo podemos eliminar 1 carácter de cualquier frecuencia solo una vez. 
No existe tal carácter eliminando el cual se pueda hacer un palíndromo.

Enfoque: Este problema se puede resolver usando la propiedad del palíndromo . Es obvio que la eliminación de las ocurrencias del mismo personaje del todo no afecta la naturaleza palindrómica. Por lo tanto, también se pueden eliminar todas las apariciones de ese carácter. Por lo tanto, verifique la string desde ambos extremos si no son iguales y luego verifique la string después de eliminar todas las apariciones del carácter en ambos extremos. Si alguna de las eliminaciones satisface la condición palindrómica entonces la respuesta es Sí ,  en caso contrario No.

Siga los pasos a continuación para resolver el problema:

• Iterar usando un ciclo en el rango de (0, N/2)
• Ahora comprueba si los caracteres de ambos extremos son iguales o no.
  • Si los personajes no son los mismos
    • Compruebe si es Palindrome después de eliminar toda la ocurrencia del carácter de ambos extremos.
    • Si eliminar ocurrencias completas de un carácter de cualquier extremo es un palíndromo, imprima «SÍ» y detenga la iteración.
• Si después de todo el recorrido, no se encuentra tal palíndromo, imprima «NO» .

A continuación se muestra la implementación del enfoque anterior:

// C++ code for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to check whether the string
// is palindrome after removal or
// neglecting character c
bool check_palindrome(string str, char c)
{
    int n = str.length(), i = 0, j = n - 1;
 
    while (i < j) {
 
        // If it is same as c neglect
        // this and move front
        if (str[i] == c)
            i++;
 
        // If it is same as c neglect
        // this and move back
        else if (str[j] == c)
            j--;
 
        // If they are not same it is
        // not a palindrome so return 0
        else if (str[i] != str[j])
            return 0;
 
        // It can be a palindrome so move
        // and check for remaining string
        else
            i++, j--;
    }
 
    return 1;
}
 
// Function to check if it is possible to
// form a palindrome after removal of
// any number of same characters once
string make_palindrome(string str)
{
    bool is_palindrome = 1;
    int n = str.length();
 
    // If n==1 || n==2 it is always possible
    if (n == 1 || n == 2) {
        return "YES";
    }
 
    // Check the character from both the ends
    // of the string
    for (int i = 0; i < n / 2; ++i) {
 
        // If the characters are not equal
        if (str[i] != str[n - 1 - i]) {
 
            // Remove str[i] and check if
            // it is a palindrome or
            // Remove str[n-i-1] and check
            // if it is a palindrome
            is_palindrome
                = check_palindrome(str, str[i])
                  || check_palindrome(
                         str, str[n - 1 - i]);
            break;
        }
    }
    if (is_palindrome)
        return "Yes";
 
    else
        return "No";
}
 
// Driver Code
int main()
{
    string S = "madem";
 
    string res = make_palindrome(S);
    cout << (res);
    return 0;
}

// Java program for the above approach
import java.util.*;
public class GFG
{
   
// Function to check whether the string
// is palindrome after removal or
// neglecting character c
static boolean check_palindrome(String str, char c)
{
    int n = str.length(), i = 0, j = n - 1;
 
    while (i < j)
    {
 
        // If it is same as c neglect
        // this and move front
        if (str.charAt(i) == c)
            i++;
 
        // If it is same as c neglect
        // this and move back
        else if (str.charAt(j) == c)
            j--;
 
        // If they are not same it is
        // not a palindrome so return 0
        else if (str.charAt(i) != str.charAt(j))
            return false;
 
        // It can be a palindrome so move
        // and check for remaining string
        else {
            i++;
            j--;
        }
    }
 
    return true;
}
 
// Function to check if it is possible to
// form a palindrome after removal of
// any number of same characters once
static String make_palindrome(String str)
{
    boolean is_palindrome = true;
    int n = str.length();
 
    // If n==1 || n==2 it is always possible
    if (n == 1 || n == 2) {
        return "YES";
    }
 
    // Check the character from both the ends
    // of the string
    for (int i = 0; i < n / 2; ++i) {
 
        // If the characters are not equal
        if (str.charAt(i) != str.charAt(n - 1 - i)) {
 
            // Remove str[i] and check if
            // it is a palindrome or
            // Remove str[n-i-1] and check
            // if it is a palindrome
            is_palindrome
                = check_palindrome(str, str.charAt(i))
                  || check_palindrome(
                         str, str.charAt(n - 1 - i));
            break;
        }
    }
    if (is_palindrome)
        return "Yes";
 
    else
        return "No";
}
 
// Driver Code
public static void main(String args[])
{
    String S = "madem";
 
    String res = make_palindrome(S);
    System.out.println(res);
}
}
 
// This code is contributed by Samim Hossain Mondal.

# Python code for the above approach
 
# Function to check whether the string
# is palindrome after removal or
# neglecting character c
def check_palindrome (str, c):
    n = len(str)
    i = 0
    j = n - 1
 
    while (i < j):
 
        # If it is same as c neglect
        # this and move front
        if (str[i] == c):
            i += 1
 
        # If it is same as c neglect
        # this and move back
        elif (str[j] == c):
            j -= 1
 
        # If they are not same it is
        # not a palindrome so return 0
        elif (str[i] != str[j]):
            return 0
 
        # It can be a palindrome so move
        # and check for remaining string
        else:
            i += 1
            j -= 1
 
 
    return 1
 
# Function to check if it is possible to
# form a palindrome after removal of
# any number of same characters once
def make_palindrome (str):
    is_palindrome = 1
    n = len(str)
 
    # If n==1 || n==2 it is always possible
    if (n == 1 or n == 2):
        return "YES"
     
    # Check the character from both the ends
    # of the string
    for i in range(n // 2):
 
        # If the characters are not equal
        if (str[i] != str[n - 1 - i]):
 
            # Remove str[i] and check if
            # it is a palindrome or
            # Remove str[n-i-1] and check
            # if it is a palindrome
            is_palindrome = check_palindrome(str, str[i]) or check_palindrome(str, str[n - 1 - i])
            break
         
    if (is_palindrome):
        return "Yes"
 
    else:
        return "No"
 
# Driver Code
S = "madem"
res = make_palindrome(S)
print(res)
 
# This code is contributed by gfgking

// C# program for the above approach
using System;
class GFG
{
   
// Function to check whether the string
// is palindrome after removal or
// neglecting character c
static bool check_palindrome(string str, char c)
{
    int n = str.Length, i = 0, j = n - 1;
 
    while (i < j)
    {
 
        // If it is same as c neglect
        // this and move front
        if (str[i] == c)
            i++;
 
        // If it is same as c neglect
        // this and move back
        else if (str[j] == c)
            j--;
 
        // If they are not same it is
        // not a palindrome so return 0
        else if (str[i] != str[j])
            return false;
 
        // It can be a palindrome so move
        // and check for remaining string
        else {
            i++;
            j--;
        }
    }
 
    return true;
}
 
// Function to check if it is possible to
// form a palindrome after removal of
// any number of same characters once
static string make_palindrome(string str)
{
    bool is_palindrome = true;
    int n = str.Length;
 
    // If n==1 || n==2 it is always possible
    if (n == 1 || n == 2) {
        return "YES";
    }
 
    // Check the character from both the ends
    // of the string
    for (int i = 0; i < n / 2; ++i) {
 
        // If the characters are not equal
        if (str[i] != str[n - 1 - i]) {
 
            // Remove str[i] and check if
            // it is a palindrome or
            // Remove str[n-i-1] and check
            // if it is a palindrome
            is_palindrome
                = check_palindrome(str, str[i])
                  || check_palindrome(
                         str, str[n - 1 - i]);
            break;
        }
    }
    if (is_palindrome)
        return "Yes";
 
    else
        return "No";
}
 
// Driver Code
public static void Main()
{
    string S = "madem";
 
    string res = make_palindrome(S);
    Console.Write(res);
}
}
 
// This code is contributed by Samim Hossain Mondal.

<script>
    // JavaScript code for the above approach
 
    // Function to check whether the string
    // is palindrome after removal or
    // neglecting character c
    const check_palindrome = (str, c) => {
        let n = str.length, i = 0, j = n - 1;
 
        while (i < j) {
 
            // If it is same as c neglect
            // this and move front
            if (str[i] == c)
                i++;
 
            // If it is same as c neglect
            // this and move back
            else if (str[j] == c)
                j--;
 
            // If they are not same it is
            // not a palindrome so return 0
            else if (str[i] != str[j])
                return 0;
 
            // It can be a palindrome so move
            // and check for remaining string
            else
                i++, j--;
        }
 
        return 1;
    }
 
    // Function to check if it is possible to
    // form a palindrome after removal of
    // any number of same characters once
    const make_palindrome = (str) => {
        let is_palindrome = 1;
        let n = str.length;
 
        // If n==1 || n==2 it is always possible
        if (n == 1 || n == 2) {
            return "YES";
        }
 
        // Check the character from both the ends
        // of the string
        for (let i = 0; i < parseInt(n / 2); ++i) {
 
            // If the characters are not equal
            if (str[i] != str[n - 1 - i]) {
 
                // Remove str[i] and check if
                // it is a palindrome or
                // Remove str[n-i-1] and check
                // if it is a palindrome
                is_palindrome
                    = check_palindrome(str, str[i])
                    || check_palindrome(
                        str, str[n - 1 - i]);
                break;
            }
        }
        if (is_palindrome)
            return "Yes";
 
        else
            return "No";
    }
 
    // Driver Code
 
    let S = "madem";
 
    let res = make_palindrome(S);
    document.write(res);
 
// This code is contributed by rakeshsahni
 
</script>

No

Complejidad de tiempo: O(N), donde N es la longitud de la string.
Complejidad espacial: O(1)