Dada una string str, necesitamos indicar los caracteres mínimos que se agregarán al frente de la string para hacer un palíndromo de strings.
Ejemplos:
Input : str = "ABC" Output : 2 We can make above string palindrome as "CBABC" by adding 'B' and 'C' at front. Input : str = "AACECAAAA"; Output : 2 We can make above string palindrome as AAAACECAAAA by adding two A's at front of string.
Enfoque ingenuo: comience a verificar la string cada vez si es un palíndromo y, si no, elimine el último carácter y vuelva a verificar. Cuando la string se reduce a un palíndromo o se vacía, la respuesta será la cantidad de caracteres eliminados desde el final hasta ahora, ya que esos caracteres podrían haberse insertado al principio de la string original en el orden que hará de la string un palíndromo. .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for getting minimum character to be
// added at front to make string palindrome
#include<bits/stdc++.h>
using namespace std;
// function for checking string is palindrome or not
bool ispalindrome(string s)
{
int l = s.length();
int j;
for(int i = 0, j = l - 1; i <= j; i++, j--)
{
if(s[i] != s[j])
return false;
}
return true;
}
// Driver code
int main()
{
string s = "BABABAA";
int cnt = 0;
int flag = 0;
while(s.length()>0)
{
// if string becomes palindrome then break
if(ispalindrome(s))
{
flag = 1;
break;
}
else
{
cnt++;
// erase the last element of the string
s.erase(s.begin() + s.length() - 1);
}
}
// print the number of insertion at front
if(flag)
cout << cnt;
}
Java
// Java program for getting minimum character to be
// added at front to make string palindrome
class GFG {
// function for checking string is palindrome or not
static boolean ispalindrome(String s) {
int l = s.length();
for (int i = 0, j = l - 1; i <= j; i++, j--) {
if (s.charAt(i) != s.charAt(j)) {
return false;
}
}
return true;
}
// Driver code
public static void main(String[] args) {
String s = "BABABAA";
int cnt = 0;
int flag = 0;
while (s.length() > 0) {
// if string becomes palindrome then break
if (ispalindrome(s)) {
flag = 1;
break;
} else {
cnt++;
// erase the last element of the string
s = s.substring(0, s.length() - 1);
//s.erase(s.begin() + s.length() - 1);
}
}
// print the number of insertion at front
if (flag == 1) {
System.out.println(cnt);
}
}
}
// This code is contributed by 29AjayKumar
Python 3
# Python 3 program for getting minimum character # to be added at front to make string palindrome # function for checking string is # palindrome or not def ispalindrome(s): l = len(s) i = 0 j = l - 1 while i <= j: if(s[i] != s[j]): return False i += 1 j -= 1 return True # Driver code if __name__ == "__main__": s = "BABABAA" cnt = 0 flag = 0 while(len(s) > 0): # if string becomes palindrome then break if(ispalindrome(s)): flag = 1 break else: cnt += 1 # erase the last element of the string s = s[:-1] # print the number of insertion at front if(flag): print(cnt) # This code is contributed by ita_c
C#
// C# program for getting minimum character to be
// added at front to make string palindrome
using System;
public class GFG {
// function for checking string is palindrome or not
static bool ispalindrome(String s) {
int l = s.Length;
for (int i = 0, j = l - 1; i <= j; i++, j--) {
if (s[i] != s[j]) {
return false;
}
}
return true;
}
// Driver code
public static void Main() {
String s = "BABABAA";
int cnt = 0;
int flag = 0;
while (s.Length > 0) {
// if string becomes palindrome then break
if (ispalindrome(s)) {
flag = 1;
break;
} else {
cnt++;
// erase the last element of the string
s = s.Substring(0, s.Length - 1);
//s.erase(s.begin() + s.length() - 1);
}
}
// print the number of insertion at front
if (flag == 1) {
Console.WriteLine(cnt);
}
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// JavaScript Program to implement
// the above approach
// function for checking string is palindrome or not
function ispalindrome(s) {
let l = s.length;
let j;
for (let i = 0, j = l - 1; i <= j; i++, j--) {
if (s[i] != s[j])
return false;
}
return true;
}
// Driver code
let s = "BABABAA";
let cnt = 0;
let flag = 0;
while (s.length > 0)
{
// if string becomes palindrome then break
if (ispalindrome(s)) {
flag = 1;
break;
}
else {
cnt++;
// erase the last element of the string
s = s.substring(0, s.length - 1);
}
}
// print the number of insertion at front
if (flag)
document.write(cnt);
// This code is contributed by Potta Lokesh
</script>
2
Complejidad temporal: O(n 2 )
Espacio Auxiliar: O(1)
Gracias Sanny Kumar por sugerir este enfoque.
Enfoque eficiente: podemos resolver este problema de manera eficiente en tiempo O (n) utilizando la array lps del algoritmo KMP .
Primero concatenamos la string concatenando la string dada, un carácter especial y el reverso de la string dada, luego obtendremos la array lps para esta string concatenada, recuerde que cada índice de la array lps representa el prefijo propio más largo que también es un sufijo. Podemos usar esta array lps para resolver el problema.
For string = AACECAAAA
Concatenated String = AACECAAAA$AAAACECAA
LPS array will be {0, 1, 0, 0, 0, 1, 2, 2, 2,
0, 1, 2, 2, 2, 3, 4, 5, 6, 7}
Aquí solo estamos interesados en el último valor de esta array lps porque nos muestra el sufijo más grande de la string invertida que coincide con el prefijo de la string original, es decir, estos muchos caracteres ya satisfacen la propiedad del palíndromo. Finalmente, el número mínimo de caracteres necesarios para convertir la string en un palíndromo es la longitud de la string de entrada menos la última entrada de nuestra array lps. Consulte el código a continuación para una mejor comprensión.
C++
// C++ program for getting minimum character to be
// added at front to make string palindrome
#include <bits/stdc++.h>
using namespace std;
// returns vector lps for given string str
vector<int> computeLPSArray(string str)
{
int M = str.length();
vector<int> lps(M);
int len = 0;
lps[0] = 0; // lps[0] is always 0
// the loop calculates lps[i] for i = 1 to M-1
int i = 1;
while (i < M)
{
if (str[i] == str[len])
{
len++;
lps[i] = len;
i++;
}
else // (str[i] != str[len])
{
// This is tricky. Consider the example.
// AAACAAAA and i = 7. The idea is similar
// to search step.
if (len != 0)
{
len = lps[len-1];
// Also, note that we do not increment
// i here
}
else // if (len == 0)
{
lps[i] = 0;
i++;
}
}
}
return lps;
}
// Method returns minimum character to be added at
// front to make string palindrome
int getMinCharToAddedToMakeStringPalin(string str)
{
string revStr = str;
reverse(revStr.begin(), revStr.end());
// Get concatenation of string, special character
// and reverse string
string concat = str + "$" + revStr;
// Get LPS array of this concatenated string
vector<int> lps = computeLPSArray(concat);
// By subtracting last entry of lps vector from
// string length, we will get our result
return (str.length() - lps.back());
}
// Driver program to test above functions
int main()
{
string str = "AACECAAAA";
cout << getMinCharToAddedToMakeStringPalin(str);
return 0;
}
Java
// Java program for getting minimum character to be
// added at front to make string palindrome
import java.util.*;
class GFG
{
// returns vector lps for given string str
public static int[] computeLPSArray(String str)
{
int n = str.length();
int lps[] = new int[n];
int i = 1, len = 0;
lps[0] = 0; // lps[0] is always 0
while (i < n)
{
if (str.charAt(i) == str.charAt(len))
{
len++;
lps[i] = len;
i++;
}
else
{
// This is tricky. Consider the example.
// AAACAAAA and i = 7. The idea is similar
// to search step.
if (len != 0)
{
len = lps[len - 1];
// Also, note that we do not increment
// i here
}
else
{
lps[i] = 0;
i++;
}
}
}
return lps;
}
// Method returns minimum character to be added at
// front to make string palindrome
static int getMinCharToAddedToMakeStringPalin(String str)
{
StringBuilder s = new StringBuilder();
s.append(str);
// Get concatenation of string, special character
// and reverse string
String rev = s.reverse().toString();
s.reverse().append("$").append(rev);
// Get LPS array of this concatenated string
int lps[] = computeLPSArray(s.toString());
return str.length() - lps[s.length() - 1];
}
// Driver Code
public static void main(String args[])
{
String str = "AACECAAAA";
System.out.println(getMinCharToAddedToMakeStringPalin(str));
}
}
// This code is contributed by Sparsh Singhal
Python3
# Python3 program for getting minimum # character to be added at the front # to make string palindrome # Returns vector lps for given string str def computeLPSArray(string): M = len(string) lps = [None] * M length = 0 lps[0] = 0 # lps[0] is always 0 # the loop calculates lps[i] # for i = 1 to M-1 i = 1 while i < M: if string[i] == string[length]: length += 1 lps[i] = length i += 1 else: # (str[i] != str[len]) # This is tricky. Consider the example. # AAACAAAA and i = 7. The idea is # similar to search step. if length != 0: length = lps[length - 1] # Also, note that we do not # increment i here else: # if (len == 0) lps[i] = 0 i += 1 return lps # Method returns minimum character # to be added at front to make # string palindrome def getMinCharToAddedToMakeStringPalin(string): revStr = string[::-1] # Get concatenation of string, # special character and reverse string concat = string + "$" + revStr # Get LPS array of this # concatenated string lps = computeLPSArray(concat) # By subtracting last entry of lps # vector from string length, we # will get our result return len(string) - lps[-1] # Driver Code if __name__ == "__main__": string = "AACECAAAA" print(getMinCharToAddedToMakeStringPalin(string)) # This code is contributed by Rituraj Jain
C#
// C# program for getting minimum character to be
// added at front to make string palindrome
using System;
using System.Text;
public class GFG{
// returns vector lps for given string str
public static int[] computeLPSArray(string str)
{
int n = str.Length;
int[] lps = new int[n];
int i = 1, len = 0;
lps[0] = 0; // lps[0] is always 0
while (i < n)
{
if (str[i] == str[len])
{
len++;
lps[i] = len;
i++;
}
else
{
// This is tricky. Consider the example.
// AAACAAAA and i = 7. The idea is similar
// to search step.
if (len != 0)
{
len = lps[len - 1];
// Also, note that we do not increment
// i here
}
else
{
lps[i] = 0;
i++;
}
}
}
return lps;
}
// Method returns minimum character to be added at
// front to make string palindrome
static int getMinCharToAddedToMakeStringPalin(string str)
{
char[] s = str.ToCharArray();
// Get concatenation of string, special character
// and reverse string
Array.Reverse( s );
string rev = new string(s);
string concat= str + "$" + rev;
// Get LPS array of this concatenated string
int[] lps = computeLPSArray(concat);
return str.Length - lps[concat.Length - 1];
}
// Driver Code
static public void Main (){
string str = "AACECAAAA";
Console.WriteLine(getMinCharToAddedToMakeStringPalin(str));
}
}
// This code is contributed by avanitrachhadiya2155
Javascript
<script>
// JavaScript program for getting minimum character to be
// added at front to make string palindrome
// returns vector lps for given string str
function computeLPSArray(str)
{
let M = str.length;
let lps = new Array(M);
let len = 0;
lps[0] = 0; // lps[0] is always 0
// the loop calculates lps[i] for i = 1 to M-1
let i = 1;
while (i < M)
{
if (str[i] == str[len])
{
len++;
lps[i] = len;
i++;
}
else // (str[i] != str[len])
{
// This is tricky. Consider the example.
// AAACAAAA and i = 7. The idea is similar
// to search step.
if (len != 0)
{
len = lps[len-1];
// Also, note that we do not increment
// i here
}
else // if (len == 0)
{
lps[i] = 0;
i++;
}
}
}
return lps;
}
// Method returns minimum character to be added at
// front to make string palindrome
function getMinCharToAddedToMakeStringPalin(str)
{
let revStr = str.split('').reverse().join('');
// Get concatenation of string, special character
// and reverse string
let concat = str + "$" + revStr;
// Get LPS array of this concatenated string
let lps = computeLPSArray(concat);
// By subtracting last entry of lps vector from
// string length, we will get our result
return (str.length - lps[lps.length-1]);
}
// Driver program to test above functions
let str = "AACECAAAA";
document.write(getMinCharToAddedToMakeStringPalin(str));
// This code is contributed by shinjanpatra
</script>
2
Complejidad temporal: O(n)
Espacio Auxiliar: O(n)
Este artículo es una contribución de Utkarsh Trivedi . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Enfoque eficiente: (Usando 2 punteros)
Podemos resolver este problema eficientemente en tiempo O(n) y espacio O(1).
Enfoque: tome el puntero izquierdo como 0 y derecho y n-1 y compare ambos caracteres
Si ambos son iguales izquierda++ y derecha–;
más
podemos pensar que tenemos que agregar elementos N-right al frente para hacer que los últimos caracteres (N-right) sean palíndromos, así que agregamos = (n-right)
Ahora de nuevo a la izquierda, apunte a 0 ya que tenemos que verificar la string desde el índice 0.
pero mientras que el carácter en la posición derecha es el mismo que el carácter de índice 0, entonces podemos agregar un carácter menos al frente y a la izquierda aumentará en 1.
Complejidad de tiempo = O(N)
Espacio Auxiliar = O(1)
C++
// C++ code to illustrate minimum characters to be added at
// front to make string palindrome using O(1) space
#include <bits/stdc++.h>
using namespace std;
int minChar(string str)
{
// Write your code here
int n = str.length();
int left = 0;
int right = n - 1;
int added = 0;
while (left < right) {
// if left and right characters are same increase
// left and decrease right pointer
if (str[left] == str[right]) {
left++;
right--;
}
// else think of adding some characters at front and
// start comparing the elements again
else {
left = 0;
added = n - right;
while (str[left] == str[right]) {
added--;
left++;
}
right--;
}
}
return added;
}
// Driver program to test above functions
int main()
{
string str = "AACECAAAA";
cout << minChar(str);
return 0;
}
// This code is contributed by sujainsu10
2
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA