Largest palindromic string possible from given strings by rearranging the characters | Python3 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 ; 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 ; Given string S and P ; Function call
from collections import defaultdict NEW_LINE def mergePalindromes ( S , P ) : NEW_LINE INDENT mapS = defaultdict ( lambda : 0 ) NEW_LINE mapP = defaultdict ( lambda : 0 ) NEW_LINE mapT = defaultdict ( lambda : 0 ) NEW_LINE n = len ( S ) NEW_LINE m = len ( P ) NEW_LINE for i in range ( n ) : NEW_LINE INDENT mapS [ ord ( S [ i ] ) ] += 1 NEW_LINE DEDENT for i in range ( m ) : NEW_LINE INDENT mapP [ ord ( P [ i ] ) ] += 1 NEW_LINE DEDENT for i in range ( ord ( ' a ' ) , ord ( ' z ' ) + 1 ) : NEW_LINE INDENT if ( mapS [ i ] % 2 == 0 ) : NEW_LINE INDENT mapT [ i ] += mapS [ i ] NEW_LINE mapS [ i ] = 0 NEW_LINE DEDENT else : NEW_LINE INDENT mapT [ i ] += mapS [ i ] - 1 NEW_LINE mapS [ i ] = 1 NEW_LINE DEDENT if ( mapP [ i ] % 2 == 0 ) : NEW_LINE INDENT mapT [ i ] += mapP [ i ] NEW_LINE mapP [ i ] = 0 NEW_LINE DEDENT else : NEW_LINE INDENT mapT [ i ] += mapP [ i ] - 1 NEW_LINE mapP [ i ] = 1 NEW_LINE DEDENT DEDENT check = 0 NEW_LINE for i in range ( ord ( ' a ' ) , ord ( ' z ' ) + 1 ) : NEW_LINE INDENT if ( mapS [ i ] > 0 and mapP [ i ] > 0 ) : NEW_LINE INDENT mapT [ i ] += 2 NEW_LINE check = 1 NEW_LINE break NEW_LINE DEDENT DEDENT half1 , half2 = " " , " " NEW_LINE for i in range ( ord ( ' a ' ) , ord ( ' z ' ) + 1 ) : NEW_LINE INDENT j = 0 NEW_LINE while ( ( 2 * j ) < mapT [ i ] ) : NEW_LINE INDENT half1 += chr ( i ) NEW_LINE half2 += chr ( i ) NEW_LINE j += 1 NEW_LINE DEDENT DEDENT half2 = half2 [ : : - 1 ] NEW_LINE if ( check ) : NEW_LINE INDENT return half1 + half2 NEW_LINE DEDENT for i in range ( ord ( ' a ' ) , ord ( ' z ' ) + 1 ) : NEW_LINE INDENT if ( mapS [ i ] > 0 or mapP [ i ] > 0 ) : NEW_LINE INDENT half1 += chr ( i ) NEW_LINE return half1 + half2 NEW_LINE DEDENT DEDENT return half1 + half2 NEW_LINE DEDENT S = " aeabb " NEW_LINE P = " dfedf " NEW_LINE print ( mergePalindromes ( S , P ) ) NEW_LINE