ENCUENTRE EL PALÍNDROMO MÁS LARGO FORMADO ELIMINANDO O MEZCLANDO CARACTERES DE UNA CADENA

Dada una cadena, encuentre el palíndromo más largo que se pueda construir eliminando o mezclando caracteres de la cadena. Devuelve solo un palíndromo si hay varias cadenas de palíndromos de mayor longitud.

Ejemplos:

  Input:    abc   Output:   a OR b OR c   Input:    aabbcc   Output:   abccba OR baccab OR cbaabc OR any other palindromic string of length 6.   Input:    abbaccd   Output:   abcdcba OR ...   Input:    aba   Output:   aba

Podemos dividir cualquier cuerda palindrómica en tres partes: inicio, mitad y final. Para una cadena palindrómica de longitud impar, digamos que 2n + 1 'beg' consta de los primeros n caracteres de la cadena. 'mid' constará de solo 1 carácter, es decir, (n + 1)ésimo carácter y 'end' constará de los últimos n caracteres de la cadena palindrómica. Para una cadena palindrómica de longitud par, 2n 'mid' siempre estará vacía. Cabe señalar que 'fin' será el inverso de 'comienzo' para que la cadena sea palíndromo.

La idea es utilizar la observación anterior en nuestra solución. Como se permite la mezcla de caracteres, el orden de los caracteres no importa en la cadena de entrada. Primero obtenemos la frecuencia de cada carácter en la cadena de entrada. Entonces, todos los caracteres que tengan una aparición par (digamos 2n) en la cadena de entrada serán parte de la cadena de salida, ya que podemos colocar fácilmente n caracteres en la cadena 'inicio' y los otros n caracteres en la cadena 'final' (preservando el orden palindrómico). Para los caracteres que tienen una aparición impar (por ejemplo, 2n + 1), completamos 'mid' con uno de todos esos caracteres. y los 2n caracteres restantes se dividen por la mitad y se agregan al principio y al final.

A continuación se muestra la implementación de la idea anterior.

C++

    // C++ program to find the longest palindrome by removing   // or shuffling characters from the given string   #include          using     namespace     std  ;   // Function to find the longest palindrome by removing   // or shuffling characters from the given string   string     findLongestPalindrome  (  string     str  )   {      // to stores freq of characters in a string      int     count  [  256  ]     =     {     0     };      // find freq of characters in the input string      for     (  int     i     =     0  ;     i      <     str  .  size  ();     i  ++  )      count  [  str  [  i  ]]  ++  ;      // Any palindromic string consists of three parts      // beg + mid + end      string     beg     =     ''       mid     =     ''       end     =     ''  ;      // solution assumes only lowercase characters are      // present in string. We can easily extend this      // to consider any set of characters      for     (  char     ch     =     'a'  ;     ch      <=     'z'  ;     ch  ++  )      {      // if the current character freq is odd      if     (  count  [  ch  ]     &     1  )      {      // mid will contain only 1 character. It      // will be overridden with next character      // with odd freq      mid     =     ch  ;      // decrement the character freq to make      // it even and consider current character      // again      count  [  ch  --  ]  --  ;      }      // if the current character freq is even      else      {      // If count is n(an even number) push      // n/2 characters to beg string and rest      // n/2 characters will form part of end      // string      for     (  int     i     =     0  ;     i      <     count  [  ch  ]  /  2     ;     i  ++  )      beg  .  push_back  (  ch  );      }      }      // end will be reverse of beg      end     =     beg  ;      reverse  (  end  .  begin  ()     end  .  end  ());      // return palindrome string      return     beg     +     mid     +     end  ;   }   // Driver code   int     main  ()   {      string     str     =     'abbaccd'  ;      cout      < <     findLongestPalindrome  (  str  );      return     0  ;   }

Java

    // Java program to find the longest palindrome by removing   // or shuffling characters from the given string   class   GFG     {   // Function to find the longest palindrome by removing   // or shuffling characters from the given string      static     String     findLongestPalindrome  (  String     str  )     {      // to stores freq of characters in a string      int     count  []     =     new     int  [  256  ]  ;      // find freq of characters in the input string      for     (  int     i     =     0  ;     i      <     str  .  length  ();     i  ++  )     {      count  [  str  .  charAt  (  i  )  ]++  ;      }      // Any palindromic string consists of three parts      // beg + mid + end      String     beg     =     ''       mid     =     ''       end     =     ''  ;      // solution assumes only lowercase characters are      // present in string. We can easily extend this      // to consider any set of characters      for     (  char     ch     =     'a'  ;     ch      <=     'z'  ;     ch  ++  )     {      // if the current character freq is odd      if     (  count  [  ch  ]     %     2     ==     1  )     {      // mid will contain only 1 character. It      // will be overridden with next character      // with odd freq      mid     =     String  .  valueOf  (  ch  );      // decrement the character freq to make      // it even and consider current character      // again      count  [  ch  --]--  ;      }     // if the current character freq is even      else     {      // If count is n(an even number) push      // n/2 characters to beg string and rest      // n/2 characters will form part of end      // string      for     (  int     i     =     0  ;     i      <     count  [  ch  ]     /     2  ;     i  ++  )     {      beg     +=     ch  ;      }      }      }      // end will be reverse of beg      end     =     beg  ;      end     =     reverse  (  end  );      // return palindrome string      return     beg     +     mid     +     end  ;      }      static     String     reverse  (  String     str  )     {      // convert String to character array       // by using toCharArray       String     ans     =     ''  ;      char  []     try1     =     str  .  toCharArray  ();      for     (  int     i     =     try1  .  length     -     1  ;     i     >=     0  ;     i  --  )     {      ans     +=     try1  [  i  ]  ;      }      return     ans  ;      }      // Driver code      public     static     void     main  (  String  []     args  )     {      String     str     =     'abbaccd'  ;      System  .  out  .  println  (  findLongestPalindrome  (  str  ));      }   }   // This code is contributed by PrinciRaj1992

Python3

    # Python3 program to find the longest palindrome by removing   # or shuffling characters from the given string   # Function to find the longest palindrome by removing   # or shuffling characters from the given string   def   findLongestPalindrome  (  strr  ):   # to stores freq of characters in a string   count   =   [  0  ]  *  256   # find freq of characters in the input string   for   i   in   range  (  len  (  strr  )):   count  [  ord  (  strr  [  i  ])]   +=   1   # Any palindromic consists of three parts   # beg + mid + end   beg   =   ''   mid   =   ''   end   =   ''   # solution assumes only lowercase characters are   # present in string. We can easily extend this   # to consider any set of characters   ch   =   ord  (  'a'  )   while   ch    <=   ord  (  'z'  ):   # if the current character freq is odd   if   (  count  [  ch  ]   &   1  ):   # mid will contain only 1 character. It   # will be overridden with next character   # with odd freq   mid   =   ch   # decrement the character freq to make   # it even and consider current character   # again   count  [  ch  ]   -=   1   ch   -=   1   # if the current character freq is even   else  :   # If count is n(an even number) push   # n/2 characters to beg and rest   # n/2 characters will form part of end   # string   for   i   in   range  (  count  [  ch  ]  //  2  ):   beg   +=   chr  (  ch  )   ch   +=   1   # end will be reverse of beg   end   =   beg   end   =   end  [::  -  1  ]   # return palindrome string   return   beg   +   chr  (  mid  )   +   end   # Driver code   strr   =   'abbaccd'   print  (  findLongestPalindrome  (  strr  ))   # This code is contributed by mohit kumar 29

    // C# program to find the longest    // palindrome by removing or   // shuffling characters from    // the given string   using     System  ;   class     GFG   {      // Function to find the longest       // palindrome by removing or       // shuffling characters from       // the given string      static     String     findLongestPalindrome  (  String     str  )         {      // to stores freq of characters in a string      int     []  count     =     new     int  [  256  ];      // find freq of characters       // in the input string      for     (  int     i     =     0  ;     i      <     str  .  Length  ;     i  ++  )         {      count  [  str  [  i  ]]  ++  ;      }      // Any palindromic string consists of       // three parts beg + mid + end      String     beg     =     ''       mid     =     ''       end     =     ''  ;      // solution assumes only lowercase       // characters are present in string.      // We can easily extend this to       // consider any set of characters      for     (  char     ch     =     'a'  ;     ch      <=     'z'  ;     ch  ++  )             {      // if the current character freq is odd      if     (  count  [  ch  ]     %     2     ==     1  )         {          // mid will contain only 1 character.       // It will be overridden with next       // character with odd freq      mid     =     String  .  Join  (  ''    ch  );      // decrement the character freq to make      // it even and consider current       // character again      count  [  ch  --  ]  --  ;      }             // if the current character freq is even      else         {          // If count is n(an even number) push      // n/2 characters to beg string and rest      // n/2 characters will form part of end      // string      for     (  int     i     =     0  ;     i      <     count  [  ch  ]     /     2  ;     i  ++  )         {      beg     +=     ch  ;      }      }      }      // end will be reverse of beg      end     =     beg  ;      end     =     reverse  (  end  );      // return palindrome string      return     beg     +     mid     +     end  ;      }      static     String     reverse  (  String     str  )         {      // convert String to character array       // by using toCharArray       String     ans     =     ''  ;      char  []     try1     =     str  .  ToCharArray  ();      for     (  int     i     =     try1  .  Length     -     1  ;     i     >=     0  ;     i  --  )         {      ans     +=     try1  [  i  ];      }      return     ans  ;      }      // Driver code      public     static     void     Main  ()         {      String     str     =     'abbaccd'  ;      Console  .  WriteLine  (  findLongestPalindrome  (  str  ));      }   }   // This code is contributed by 29AjayKumar

JavaScript

     <  script  >   // Javascript program to find the    // longest palindrome by removing   // or shuffling characters from    // the given string   // Function to find the longest    // palindrome by removing   // or shuffling characters from   // the given string      function     findLongestPalindrome  (  str  )      {      // to stores freq of characters       // in a string      let     count     =     new     Array  (  256  );      for  (  let     i  =  0  ;  i   <  256  ;  i  ++  )      {      count  [  i  ]  =  0  ;      }          // find freq of characters in       // the input string      for     (  let     i     =     0  ;     i      <     str  .  length  ;     i  ++  )     {      count  [  str  [  i  ].  charCodeAt  (  0  )]  ++  ;      }          // Any palindromic string consists      // of three parts      // beg + mid + end      let     beg     =     ''       mid     =     ''       end     =     ''  ;          // solution assumes only       // lowercase characters are      // present in string.       // We can easily extend this      // to consider any set of characters      for     (  let     ch     =     'a'  .  charCodeAt  (  0  );         ch      <=     'z'  .  charCodeAt  (  0  );     ch  ++  )     {      // if the current character freq is odd      if     (  count  [  ch  ]     %     2     ==     1  )     {      // mid will contain only 1 character. It      // will be overridden with next character      // with odd freq      mid     =     String  .  fromCharCode  (  ch  );          // decrement the character freq to make      // it even and consider current character      // again      count  [  ch  --  ]  --  ;      }     // if the current character freq is even      else     {      // If count is n(an even number) push      // n/2 characters to beg string and rest      // n/2 characters will form part of end      // string      for     (  let     i     =     0  ;     i      <     count  [  ch  ]     /     2  ;     i  ++  )         {      beg     +=     String  .  fromCharCode  (  ch  );      }      }      }          // end will be reverse of beg      end     =     beg  ;      end     =     reverse  (  end  );          // return palindrome string      return     beg     +     mid     +     end  ;      }          function     reverse  (  str  )      {      // convert String to character array       // by using toCharArray       let     ans     =     ''  ;      let     try1     =     str  .  split  (  ''  );          for     (  let     i     =     try1  .  length     -     1  ;     i     >=     0  ;     i  --  )     {      ans     +=     try1  [  i  ];      }      return     ans  ;      }          // Driver code      let     str     =     'abbaccd'  ;      document  .  write  (  findLongestPalindrome  (  str  ));          // This code is contributed by unknown2108        <  /script>

Producción

abcdcba

Complejidad del tiempo de la solución anterior es O(n) donde n es la longitud de la cadena. Dado que el número de caracteres del alfabeto es constante, no contribuyen al análisis asintótico.
Espacio auxiliar utilizado por el programa es M donde M es el número de caracteres ASCII.