Reorganizar la string para obtener la substring palindrómica más larga

Dada la string str , la tarea es reorganizar la string dada para obtener la substring palindrómica más larga .

Ejemplos:

Entrada: str = “geeksforgeeks”
Salida: eegksfskgeeor
Explicación: eegksfskgee es la substring palindrómica más larga después de reorganizar la string.
Por lo tanto, la salida requerida es eegksfskgeeor.

Entrada: str = «ingeniería»
Salida: eginenigenr

Enfoque: El problema se puede resolver usando Hashing . La idea es contar la frecuencia de cada carácter de la string dada . Si el recuento de ocurrencias de un carácter excede 1, agregue la mitad (valor mínimo) de su frecuencia en el lado izquierdo de la string resultante y la mitad restante en el lado derecho de la string resultante. Para los caracteres restantes, agregue un carácter en el medio de la string resultante y el resto al principio o al final de la string resultante. Siga los pasos a continuación para resolver el problema:

  1. Inicialice una array , digamos hash[256] para almacenar la frecuencia de cada carácter .
  2. Para agregar de manera eficiente los caracteres en ambos lados de la string resultante, inicialice tres strings res1, res2 y res3 .
  3. La string res1 almacena la mitad izquierda de la substring palindrómica más larga posible, res2 almacena la mitad derecha de la substring palindrómica más larga posible y res3 almacena los caracteres restantes.
  4. Recorra la array hash[] y para el carácter, digamos hash[i] , verifique si su frecuencia es mayor que 1 o no. Si se determina que es cierto, agregue el carácter floor(hash[i]/2) veces en res1 y floor(hash[i]/2) veces en res2 .
  5. De lo contrario, agregue el primer carácter para no cumplir la condición anterior a res1 y todos los caracteres restantes a res3 .
  6. Finalmente, devuelve la string res1 + reverse(res2) + res3 .

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

C++

// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to rearrange the string to
// get the longest palindromic substring
string longestPalinSub(string str) {
     
    // Stores the length of str
    int N = str.length();
     
    // Store the count of occurrence
    // of each character
    int hash[256] = {0};
     
    // Traverse the string, str
    for(int i = 0; i < N;
    i++) {
         
        // Count occurrence of
        // each character
        hash[str[i]]++;
    }
     
    // Store the left half of the
    // longest palindromic substring
    string res1 = "";
     
    // Store the right half of the
    // longest palindromic substring
    string res2 = "";
     
    // Traverse the array, hash[]
    for(int i = 0; i< 256; i++) {
        // Append half of the
        // characters  to res1
        for(int j = 0; j < hash[i] / 2;
        j++) {
            res1.push_back(i);
        }
         
        // Append half of the
        // characters  to res2
        for(int j = (hash[i] + 1)/2;
        j < hash[i]; j++) {
            res2.push_back(i);
        }
    }
     
    // reverse string res2 to make
    // res1 + res2 palindrome
    reverse(res2.begin(), res2.end());
     
    // Store the remaining characters
    string res3;
     
    // Check If any odd character
    // appended to the middle of
    // the resultant string or not
    bool f = false;
     
    // Append all the character which
    // occurs odd number of times
    for(int i = 0; i < 256; i++) {
         
        // If count of occurrence
        // of characters is odd
        if(hash[i]%2) {
            if(!f) {
               res1.push_back(i);
               f = true;
            }
            else {
                res3.push_back(i);
            }
        }
    }
     
    return (res1 + res2 + res3);   
}
 
// Driver Code
int main() {
    string str = "geeksforgeeks";
    cout<<longestPalinSub(str);
}

Java

// Java program to implement
// the above approach
import java.util.*;
 
class GFG{
     
// Function to rearrange the string to 
// get the longest palindromic substring
static String longestPalinSub(String str)
{
     
    // Stores the length of str
    int N = str.length();
       
    // Store the count of occurrence
    // of each character
    int[] hash = new int[256];
       
    // Traverse the string, str
    for(int i = 0; i < N; i++)
    {
         
        // Count occurrence of 
        // each character
        hash[str.charAt(i)]++;
    }
       
    // Store the left half of the 
    // longest palindromic substring
    StringBuilder res1 = new StringBuilder();
       
    // Store the right half of the 
    // longest palindromic substring
    StringBuilder res2 = new StringBuilder();
       
    // Traverse the array, hash[]
    for(int i = 0; i < 256; i++)
    {
         
        // Append half of the 
        // characters  to res1
        for(int j = 0; j < hash[i] / 2; j++)
        {
            res1.append((char)i);
        }
           
        // Append half of the 
        // characters to res2
        for(int j = (hash[i] + 1) / 2;
                j < hash[i]; j++)
        {
            res2.append((char)i);
        }
    }
     
    // reverse string res2 to make
    // res1 + res2 palindrome
    StringBuilder tmp = res2.reverse();
       
    // Store the remaining characters
    StringBuilder res3 = new StringBuilder();
       
    // Check If any odd character
    // appended to the middle of 
    // the resultant string or not 
    boolean f = false;
       
    // Append all the character which
    // occurs odd number of times 
    for(int i = 0; i < 256; i++)
    {
         
        // If count of occurrence 
        // of characters is odd
        if (hash[i] % 2 == 1)
        {
            if (!f)
            {
               res1.append((char)i);
               f = true; 
            }
            else
            {
                res3.append((char)i);
            }
        }
    }
       
    return (res1.toString() +
             tmp.toString() +
            res3.toString());    
}
     
// Driver code
public static void main (String[] args)
{
    String str = "geeksforgeeks";
     
    System.out.println(longestPalinSub(str));
}
}
 
// This code is contributed by offbeat

Python3

# Python 3 program to implement
# the above approach
 
# Function to rearrange the
# string to get the longest
# palindromic substring
def longestPalinSub(st):
 
    # Stores the length of
    # str
    N = len(st)
 
    # Store the count of
    # occurrence of each
    # character
    hash1 = [0] * 256
 
    # Traverse the string,
    # str
    for i in range(N):
 
        # Count occurrence of
        # each character
        hash1[ord(st[i])] += 1
 
    # Store the left half of the
    # longest palindromic substring
    res1 = ""
 
    # Store the right half of the
    # longest palindromic substring
    res2 = ""
 
    # Traverse the array, hash[]
    for i in range(256):
       
        # Append half of the
        # characters  to res1
        for j in range(hash1[i] // 2):
            res1 += chr(i)
 
        # Append half of the
        # characters  to res2
        for j in range((hash1[i] + 1)//2,
                        hash1[i]):
            res2 += chr(i)
 
    # reverse string res2 to make
    # res1 + res2 palindrome
    p = list(res2)
    p.reverse()
    res2 = ''.join(p)
 
    # Store the remaining characters
    res3 = ""
 
    # Check If any odd character
    # appended to the middle of
    # the resultant string or not
    f = False
 
    # Append all the character which
    # occurs odd number of times
    for i in range(256):
 
        # If count of occurrence
        # of characters is odd
        if(hash1[i] % 2):
            if(not f):
                res1 += chr(i)
                f = True
            else:
                res3 += chr(i)
 
    return (res1 + res2 + res3)
 
# Driver Code
if __name__ == "__main__":
 
    st = "geeksforgeeks"
    print(longestPalinSub(st))
 
# This code is contributed by Chitranayal

C#

// C# program to implement
// the above approach
using System;
using System.Text;
class GFG{
 
// Reverse string
static String reverse(String input)
{
  char[] a = input.ToCharArray();
  int l, r = a.Length - 1;
  for (l = 0; l < r; l++, r--)
  {
    char temp = a[l];
    a[l] = a[r];
    a[r] = temp;
  }
  return String.Join("", a);
}
   
// Function to rearrange the string to 
// get the longest palindromic substring
static String longestPalinSub(String str)
{
  // Stores the length of str
  int N = str.Length;
 
  // Store the count of occurrence
  // of each character
  int[] hash = new int[256];
 
  // Traverse the string, str
  for(int i = 0; i < N; i++)
  {
    // Count occurrence of 
    // each character
    hash[str[i]]++;
  }
 
  // Store the left half of the 
  // longest palindromic substring
  StringBuilder res1 = new StringBuilder();
 
  // Store the right half of the 
  // longest palindromic substring
  StringBuilder res2 = new StringBuilder();
 
  // Traverse the array, hash[]
  for(int i = 0; i < 256; i++)
  {
    // Append half of the 
    // characters  to res1
    for(int j = 0; j < hash[i] / 2; j++)
    {
      res1.Append((char)i);
    }
 
    // Append half of the 
    // characters to res2
    for(int j = (hash[i] + 1) / 2;
            j < hash[i]; j++)
    {
      res2.Append((char)i);
    }
  }
 
  // reverse string res2 to make
  // res1 + res2 palindrome
  String tmp = reverse(res2.ToString());
 
  // Store the remaining characters
  StringBuilder res3 = new StringBuilder();
 
  // Check If any odd character
  // appended to the middle of 
  // the resultant string or not 
  bool f = false;
 
  // Append all the character which
  // occurs odd number of times 
  for(int i = 0; i < 256; i++)
  {
    // If count of occurrence 
    // of characters is odd
    if (hash[i] % 2 == 1)
    {
      if (!f)
      {
        res1.Append((char)i);
        f = true; 
      }
      else
      {
        res3.Append((char)i);
      }
    }
  }
  return (res1.ToString() +
          tmp.ToString() +
          res3.ToString());    
}
     
// Driver code
public static void Main(String[] args)
{
  String str = "geeksforgeeks";
  Console.WriteLine(longestPalinSub(str));
}
}
 
// This code is contributed by Rajput-Ji

Javascript

<script>
 
// Javascript program to implement
// the above approach
 
// Function to rearrange the string to
// get the longest palindromic substring
function longestPalinSub(str)
{
     
    // Stores the length of str
    var N = str.length;
     
    // Store the count of occurrence
    // of each character
    var hash = Array(256).fill(0);
     
    // Traverse the string, str
    for(var i = 0; i < N; i++)
    {
         
        // Count occurrence of
        // each character
        hash[str[i].charCodeAt(0)]++;
    }
     
    // Store the left half of the
    // longest palindromic substring
    var res1 = [];
     
    // Store the right half of the
    // longest palindromic substring
    var res2 = [];
     
    // Traverse the array, hash[]
    for(var i = 0; i< 256; i++)
    {
         
        // Append half of the
        // characters  to res1
        for(var j = 0; j < parseInt(hash[i] / 2); j++)
        {
            res1.push(String.fromCharCode(i));
        }
         
        // Append half of the
        // characters  to res2
        for(var j = parseInt((hash[i] + 1) / 2);
                j < hash[i]; j++)
        {
            res2.push(String.fromCharCode(i));
        }
    }
     
    // Reverse string res2 to make
    // res1 + res2 palindrome
    res2 = res2.reverse();
     
    // Store the remaining characters
    var res3 = [];
     
    // Check If any odd character
    // appended to the middle of
    // the resultant string or not
    var f = false;
     
    // Append all the character which
    // occurs odd number of times
    for(var i = 0; i < 256; i++)
    {
         
        // If count of occurrence
        // of characters is odd
        if (hash[i] % 2)
        {
            if(!f)
            {
                res1.push(String.fromCharCode(i));
                f = true;
            }
            else
            {
                res3.push(String.fromCharCode(i));
            }
        }
    }
    return (res1.join('') +
            res2.join('') +
            res3.join(''));   
}
 
// Driver Code
var str = "geeksforgeeks";
document.write(longestPalinSub(str));
 
// This code is contributed by noob2000
 
</script>
Producción

eegksfskgeeor

Complejidad temporal: O(N)
Espacio auxiliar: O(1)

Publicación traducida automáticamente

Artículo escrito por armaan48 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *