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