Palíndromo más largo formado al concatenar y reordenar strings de igual longitud

Dada una array arr[] que consta de N strings de igual longitud M , la tarea es crear el palíndromo más largo concatenando las strings. También se puede reordenar y descartar algunas strings del conjunto de strings dado.
Ejemplos: 
 

Entrada: N = 3, arr[] = { “tab”, “one”, “bat” }, M = 3 
Salida: tabbat 
Explicación:  al
combinar “tab” y “bat” del conjunto dado de strings de entrada, el se forma la cuerda palindrómica más larga.
Entrada: N = 4, arr[] = { “oo”, “ox”, “xo”, “xx” }, M = 2 
Salida: oxxxxo 
 

Observación: Supongamos que elegimos algunas K strings de la array dada y la string que obtenemos después de elegir esas K strings es un palíndromo. Entonces, la observación que debe hacerse para los posibles valores de K son: 
 

• K es par: Entonces para cada entero x (1 <= x <= K/2): 
   

Sx = rev(SK - x + 1)

• Por ejemplo, si las cuerdas que forman el palíndromo más largo son S ₁ = “tab”, S ₂ = “ab”, S ₃ = “ba”, S ₄ = “bat”. Aquí, K = 4. Por lo tanto, S ₁ = rev(S ₄ ) y S ₂ = rev(S ₃ ).
• K es impar: además de la observación anterior, la string central S _(K+1)/2 es un palíndromo.

Enfoque: claramente, a partir de la observación anterior, para obtener el palíndromo más grande, la array dada también debe contener el reverso de la string. Por lo tanto, para cada string, encontramos si hay otra string que sea su reverso. Si existe, agregamos este par de strings al extremo izquierdo y derecho respectivamente. Si hay una o más cuerdas que son palíndromos, elija cualquiera de ellas y colóquela en el medio.
A continuación se muestra la implementación del enfoque anterior:
 

// C++ program to find the
// Longest palindrome that can be formed
// by concatenating and reordering
// given N strings of equal length
#include <bits/stdc++.h>
using namespace std;
 
// Function to print the longest palindrome
void printPalindrome(vector<string> left,
                     string mid, vector<string> right)
{
    // Printing every string in left vector
    for (string x : left)
        cout << x;
 
    // Printing the palindromic string
    // in the middle
    cout << mid;
 
    // Printing the reverse of the right vector
    // to make the final output palindromic
    reverse(right.begin(), right.end());
    for (string x : right)
        cout << x;
 
    cout << endl;
}
 
// Function to find and print the
// longest palindrome that can be formed
void findPalindrome(vector<string>& S, int N, int M)
{
    set<string> dict;
    for (int i = 0; i < M; i++) {
        cin >> S[i];
        // Inserting each string in the set
        dict.insert(S[i]);
    }
 
    // Vectors to add the strings
    // in the left and right side
    vector<string> left, right;
 
    // To add the already present palindrome
    // string in the middle of the solution
    string mid;
 
    // Iterating through all the given strings
    for (int i = 0; i < N; i++) {
        string t = S[i];
        reverse(t.begin(), t.end());
 
        // If the string is a palindrome
        // it is added in the middle
        if (t == S[i])
            mid = t;
 
        // Checking if the reverse
        // of the string is already
        // present in the set
        else if (dict.find(t) != dict.end()) {
            left.push_back(S[i]);
            right.push_back(t);
            dict.erase(S[i]);
            dict.erase(t);
        }
    }
 
    printPalindrome(left, mid, right);
}
 
// Driver code
int main()
{
    vector<string> S{ "tab", "one", "bat" };
    int M = 3;
    int N = S.size();
    findPalindrome(S, N, M);
}

// Java program to find the
// Longest palindrome that can be formed
// by concatenating and reordering
// given N Strings of equal length
import java.util.*;
 
class GFG{
  
// Function to print the longest palindrome
static void printPalindrome(Vector<String> left,
                     String mid, Vector<String> right)
{
    // Printing every String in left vector
    for (String x : left)
        System.out.print(x);
  
    // Printing the palindromic String
    // in the middle
    System.out.print(mid);
  
    // Printing the reverse of the right vector
    // to make the final output palindromic
    Collections.reverse(right);
    for (String x : right)
        System.out.print(x);
  
    System.out.println();
}
  
// Function to find and print the
// longest palindrome that can be formed
static void findPalindrome(Vector<String> S, int N, int M)
{
    HashSet<String> dict = new HashSet<String>();
    for (int i = 0; i < M; i++) {
        // Inserting each String in the set
        dict.add(S.get(i));
    }
  
    // Vectors to add the Strings
    // in the left and right side
    Vector<String> left = new Vector<String>(), right = new Vector<String>();
  
    // To add the already present palindrome
    // String in the middle of the solution
    String mid="";
  
    // Iterating through all the given Strings
    for (int i = 0; i < N; i++) {
        String t = S.get(i);
        t = reverse(t);
  
        // If the String is a palindrome
        // it is added in the middle
        if (t == S.get(i))
            mid = t;
  
        // Checking if the reverse
        // of the String is already
        // present in the set
        else if (dict.contains(t)) {
            left.add(S.get(i));
            right.add(t);
            dict.remove(S.get(i));
            dict.remove(t);
        }
    }
  
    printPalindrome(left, mid, right);
}
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.valueOf(a);
}
// Driver code
public static void main(String[] args)
{
    String arr[] = { "tab", "one", "bat" };
    Vector<String> S = new Vector<String>(Arrays.asList(arr));
    int M = 3;
    int N = S.size();
    findPalindrome(S, N, M);
}
}
 
// This code contributed by PrinciRaj1992

# Function to print the longest palindrome
def printPalindrome(left,mid,right):
 
    # Printing every string in left vector
    for x in left:
        print(x, end="")
 
    # Printing the palindromic string
    # in the middle
    print(mid, end="")
 
    # Printing the reverse of the right vector
    # to make the final output palindromic
    right = right[::-1]
    for x in right:
        print(x, end = "")
 
    print('\n', end = "")
 
# Function to find and print the
# longest palindrome that can be formed
def findPalindrome(S, N, M):
    d = set()
    for i in range(M):
        # Inserting each string in the set
        d.add(S[i])
 
    # Vectors to add the strings
    # in the left and right side
    left = []
    right = []
 
    # To add the already present palindrome
    # string in the middle of the solution
    mid = ""
 
    # Iterating through all the given strings
    for i in range(N):
        t = S[i]
        t = t[::-1]
 
        # If the string is a palindrome
        # it is added in the middle
        if (t == S[i]):
            mid = t
 
        # Checking if the reverse
        # of the string is already
        # present in the set
        elif (t in d):
            left.append(S[i])
            right.append(t)
            d.remove(S[i])
            d.remove(t)
 
    printPalindrome(left, mid, right)
 
# Driver code
if __name__ == '__main__':
    S = ["tab", "one", "bat"]
    M = 3
    N = len(S)
    findPalindrome(S, N, M)
 
# This code is contributed by Surendra_Gangwar

// C# program to find the
// longest palindrome that can be formed
// by concatenating and reordering
// given N Strings of equal length
using System;
using System.Collections.Generic;
 
class GFG{
 
// Function to print the longest palindrome
static void printPalindrome(List<String> left,
                    String mid, List<String> right)
{
    // Printing every String in left vector
    foreach (String x in left)
        Console.Write(x);
 
    // Printing the palindromic String
    // in the middle
    Console.Write(mid);
 
    // Printing the reverse of the right vector
    // to make the readonly output palindromic
    right.Reverse();
    foreach (String x in right)
        Console.Write(x);
 
    Console.WriteLine();
}
 
// Function to find and print the
// longest palindrome that can be formed
static void findPalindrome(List<String> S, int N, int M)
{
    HashSet<String> dict = new HashSet<String>();
    for (int i = 0; i < M; i++) {
         
        // Inserting each String in the set
        dict.Add(S[i]);
    }
 
    // Lists to add the Strings
    // in the left and right side
    List<String> left = new List<String>(),
    right = new List<String>();
 
    // To add the already present palindrome
    // String in the middle of the solution
    String mid="";
 
    // Iterating through all the given Strings
    for (int i = 0; i < N; i++) {
        String t = S[i];
        t = reverse(t);
 
        // If the String is a palindrome
        // it is added in the middle
        if (t == S[i])
            mid = t;
 
        // Checking if the reverse
        // of the String is already
        // present in the set
        else if (dict.Contains(t)) {
            left.Add(S[i]);
            right.Add(t);
            dict.Remove(S[i]);
            dict.Remove(t);
        }
    }
 
    printPalindrome(left, mid, right);
}
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);
}
 
// Driver code
public static void Main(String[] args)
{
    String []arr = { "tab", "one", "bat" };
    List<String> S = new List<String>(arr);
    int M = 3;
    int N = S.Count;
    findPalindrome(S, N, M);
}
}
 
// This code is contributed by Princi Singh

<script>
 
// Function to print the longest palindrome
function printPalindrome(left,mid,right){
 
    // Printing every string in left vector
    for(let x of left)
        document.write(x,"")
 
    // Printing the palindromic string
    // in the middle
    document.write(mid,"")
 
    // Printing the reverse of the right vector
    // to make the final output palindromic
    right = right.reverse()
    for(let x of right){
        document.write(x,"")
    }
 
    document.write("</br>","")
}
 
// Function to find and print the
// longest palindrome that can be formed
function findPalindrome(S, N, M){
    let d = new Set()
    for(let i=0;i<M;i++)
        // Inserting each string in the set
        d.add(S[i])
 
    // Vectors to add the strings
    // in the left and right side
    let left = []
    let right = []
 
    // To add the already present palindrome
    // string in the middle of the solution
    let mid = ""
 
    // Iterating through all the given strings
    for(let i=0;i<N;i++){
        let t = S[i]
        t = t.split("").reverse().join("")
 
        // If the string is a palindrome
        // it is added in the middle
        if (t == S[i])
            mid = t
 
        // Checking if the reverse
        // of the string is already
        // present in the set
        else if(d.has(t)){
            left.push(S[i])
            right.push(t)
            d.delete(S[i])
            d.delete(t)
        }
    }
 
    printPalindrome(left, mid, right)
}
 
// Driver code
 
let S = ["tab", "one", "bat"]
let M = 3
let N = S.length
findPalindrome(S, N, M)
 
// This code is contributed by shinjanpatra
 
</script>

tabbat