Dada una string S , la tarea es si una string puede convertirse en palíndromo después de eliminar las ocurrencias del mismo carácter, cualquier número de veces .
Ejemplos:
Entrada : S = “abczdzacb”
Salida : Sí
Explicación : elimine la primera y la segunda aparición del carácter ‘a’, la string S se convierte en “bczdzcb”, que es un palíndromo.
Entrada : S = “madem”
Salida : No
Enfoque: la tarea se puede resolver iterando sobre cada carácter único en la string dada y eliminando sus ocurrencias donde haya una discrepancia , si se encuentra un palíndromo válido, después de eliminar las ocurrencias del mismo carácter cualquier cantidad de veces, devuelve » Sí «. ” de lo contrario devuelve “ No “.
Siga los pasos a continuación para resolver el problema:
- Comience a iterar sobre cada carácter único de la string, cuyas ocurrencias se eliminarán
- Use la técnica de dos punteros , para verificar si hay una falta de coincidencia, coloque l al comienzo de la string y r al final de la string
- Si S[l] == S[r] , incremente l y disminuya r .
- Si S[l]!= S[r], comprueba si S[l[ == char, haz l++, si S[r] == char, haz r–
- Si ninguna de las condiciones se cumple, significa que lo dado no se puede convertir en un palíndromo
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 check if a palindrome is
// possible or not
string isPossible(string S)
{
// Stores the length of string
int n = (int)S.length();
// Stores the unique characters in
// the string
set<char> st;
for (int i = 0; i < n; i++) {
st.insert(S[i]);
}
// Check if valid palindrome is
// possible or not
bool check = false;
// Iterating over unique characters
// of the string
for (auto ele : st) {
// Pointers to check the condition
int low = 0, high = n - 1;
bool flag = true;
// Iterating over the string
for (int i = 0; i < n; i++) {
if (S[low] == S[high]) {
// Updating low and high
low++;
high--;
}
else {
if (S[low] == ele) {
// Updating low
low++;
}
else if (S[high] == ele) {
// Updating high
high--;
}
else {
// It is impossible
// to make palindrome
// by removing
// occurrences of char
flag = false;
break;
}
}
}
// If palindrome is formed
// break the loop
if (flag == true) {
check = true;
break;
}
}
if (check)
return "Yes";
else
return "No";
}
// Driver Code
int main()
{
string S = "abczdzacb";
cout << isPossible(S);
return 0;
}
Java
// Java code for the above approach
import java.util.*;
class GFG
{
// Function to check if a palindrome is
// possible or not
static String isPossible(String S)
{
// Stores the length of string
int n = S.length();
// Stores the unique characters in
// the string
Set<Character> st = new HashSet<Character>();
for (int i = 0; i < n; i++) {
st.add(S.charAt(i));
}
// Check if valid palindrome is
// possible or not
boolean check = false;
// Iterating over unique characters
// of the string
for (Character ele : st) {
// Pointers to check the condition
int low = 0, high = n - 1;
boolean flag = true;
// Iterating over the string
for (int i = 0; i < n; i++) {
if (S.charAt(low) == S.charAt(high)) {
// Updating low and high
low++;
high--;
}
else {
if (S.charAt(low) == ele) {
// Updating low
low++;
}
else if (S.charAt(high)== ele) {
// Updating high
high--;
}
else {
// It is impossible
// to make palindrome
// by removing
// occurrences of char
flag = false;
break;
}
}
}
// If palindrome is formed
// break the loop
if (flag == true) {
check = true;
break;
}
}
if (check)
return "Yes";
else
return "No";
}
// Driver Code
public static void main (String[] args) {
String S = "abczdzacb";
System.out.println(isPossible(S));
}
}
// This code is contributed by Potta Lokesh
Python3
# python program for the above approach # Function to check if a palindrome is # possible or not def isPossible(S): # Stores the length of string n = len(S) # Stores the unique characters in # the string st = set() for i in range(0, n): st.add(S[i]) # Check if valid palindrome is # possible or not check = False # Iterating over unique characters # of the string for ele in st: # Pointers to check the condition low = 0 high = n - 1 flag = True # Iterating over the string for i in range(0, n): if (S[low] == S[high]): # Updating low and high low += 1 high -= 1 else: if (S[low] == ele): # Updating low low += 1 elif (S[high] == ele): # Updating high high -= 1 else: # It is impossible # to make palindrome # by removing # occurrences of char flag = False break # If palindrome is formed # break the loop if (flag == True): check = True break if (check): return "Yes" else: return "No" # Driver Code if __name__ == "__main__": S = "abczdzacb" print(isPossible(S)) # This code is contributed by rakeshsahni
C#
// C# code for the above approach
using System;
using System.Collections.Generic;
public class GFG
{
// Function to check if a palindrome is
// possible or not
static String isPossible(String S)
{
// Stores the length of string
int n = S.Length;
// Stores the unique characters in
// the string
HashSet<char> st = new HashSet<char>();
for (int i = 0; i < n; i++) {
st.Add(S[i]);
}
// Check if valid palindrome is
// possible or not
bool check = false;
// Iterating over unique characters
// of the string
foreach (char ele in st) {
// Pointers to check the condition
int low = 0, high = n - 1;
bool flag = true;
// Iterating over the string
for (int i = 0; i < n; i++) {
if (S[low] == S[high]) {
// Updating low and high
low++;
high--;
}
else {
if (S[low] == ele) {
// Updating low
low++;
}
else if (S[high]== ele) {
// Updating high
high--;
}
else {
// It is impossible
// to make palindrome
// by removing
// occurrences of char
flag = false;
break;
}
}
}
// If palindrome is formed
// break the loop
if (flag == true) {
check = true;
break;
}
}
if (check)
return "Yes";
else
return "No";
}
// Driver Code
public static void Main(String[] args) {
String S = "abczdzacb";
Console.WriteLine(isPossible(S));
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// Javascript program for the above approach
// Function to check if a palindrome is
// possible or not
function isPossible(S)
{
// Stores the length of string
let n = S.length;
// Stores the unique characters in
// the string
let st = new Set();
for (let i = 0; i < n; i++) {
st.add(S[i]);
}
// Check if valid palindrome is
// possible or not
let check = false;
// Iterating over unique characters
// of the string
for (ele of st) {
// Pointers to check the condition
let low = 0, high = n - 1;
let flag = true;
// Iterating over the string
for (let i = 0; i < n; i++) {
if (S[low] == S[high]) {
// Updating low and high
low++;
high--;
}
else {
if (S[low] == ele) {
// Updating low
low++;
}
else if (S[high] == ele) {
// Updating high
high--;
}
else {
// It is impossible
// to make palindrome
// by removing
// occurrences of char
flag = false;
break;
}
}
}
// If palindrome is formed
// break the loop
if (flag == true) {
check = true;
break;
}
}
if (check)
return "Yes";
else
return "No";
}
// Driver Code
let S = "abczdzacb";
document.write(isPossible(S));
// This code is contributed by saurabh_jaiswal.
</script>
Producción:
Yes
Tiempo Complejidad :O(n*26)
Espacio Auxiliar : O(n)
Publicación traducida automáticamente
Artículo escrito por subhankarjadab y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA