Largest palindromic string possible from given strings by rearranging the characters | C ++ program for the above approach ; Function to find largest palindrome possible from S and P after rearranging characters to make palindromic string T ; Using unordered_map to store frequency of elements mapT will have freq of elements of T ; Size of both the strings ; Take all character in mapT which occur even number of times in respective strings & simultaneously update number of characters left in map ; Check if a unique character is present in both string S and P ; Making string T in two halves half1 - first half half2 - second half ; Reverse the half2 to attach with half1 to make palindrome T ; If same unique element is present in both S and P , then taking that only which is already taken through mapT ; If same unique element is not present in S and P , then take characters that make string T lexicographically smallest ; If no unique element is present in both string S and P ; Driver Code ; Given two strings S and P ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; string mergePalindromes ( string S , string P ) { unordered_map < char , int > mapS , mapP , mapT ; int n = S . size ( ) , m = P . size ( ) ; for ( int i = 0 ; i < n ; i ++ ) { mapS [ S [ i ] ] ++ ; } for ( int i = 0 ; i < m ; i ++ ) { mapP [ P [ i ] ] ++ ; } for ( char i = ' a ' ; i <= ' z ' ; i ++ ) { if ( mapS [ i ] % 2 == 0 ) { mapT [ i ] += mapS [ i ] ; mapS [ i ] = 0 ; } else { mapT [ i ] += mapS [ i ] - 1 ; mapS [ i ] = 1 ; } if ( mapP [ i ] % 2 == 0 ) { mapT [ i ] += mapP [ i ] ; mapP [ i ] = 0 ; } else { mapT [ i ] += mapP [ i ] - 1 ; mapP [ i ] = 1 ; } } int check = 0 ; for ( char i = ' a ' ; i <= ' z ' ; i ++ ) { if ( mapS [ i ] > 0 && mapP [ i ] > 0 ) { mapT [ i ] += 2 ; check = 1 ; break ; } } string half1 = " " , half2 = " " ; for ( char i = ' a ' ; i <= ' z ' ; i ++ ) { for ( int j = 0 ; ( 2 * j ) < mapT [ i ] ; j ++ ) { half1 += i ; half2 += i ; } } reverse ( half2 . begin ( ) , half2 . end ( ) ) ; if ( check ) { return half1 + half2 ; } for ( char i = ' a ' ; i <= ' z ' ; i ++ ) { if ( mapS [ i ] > 0 mapP [ i ] > 0 ) { half1 += i ; return half1 + half2 ; } } return half1 + half2 ; } int main ( ) { string S = " aeabb " ; string P = " dfedf " ; cout << mergePalindromes ( S , P ) ; return 0 ; }