0 like 0 dislike
2,780 views
| 2,780 views

0 like 0 dislike

Question Level: Medium - Hard
Merging Palindromes
Given two strings, find all palindromes that can be formed with the letters of each string. From those palindromes, select one from each set that, when combined and rearranged, produces the longest palindrome posslble. If there are multiple palindromes of that length, choose the alphabeticaly smallest of them.
Example
s1 = 'aabbc'
s2 = 'ddefefq'

by Expert (46,090 points)
0 like 0 dislike
``````def merging(a ,b):
count_a =[0]*26
count_b=[0]*26

for ch in a:
count_a[ord(ch)-ord('a')]+=1

for ch in b:
count_b[ord(ch)-ord('a')]+=1

mid=''
res=''
for i in range(26):

curr = chr(i+ord('a'))

if count_a[i]%2==1 and count_b[i]%2==1 and len(mid)<2:
mid=curr*2

if (count_a[i]%2==1 or count_b[i]%2==1) and mid=='':
mid=curr

res+=(curr*(count_a[i]//2+count_b[i]//2))

# sort the res
if len(mid)==2:
res=''.join(sorted(res+mid[0] ))
return res+res[::-1]

return res+mid+res[::-1]``````
by Expert (46,090 points)
0 like 0 dislike
• find all even char in both string
• if any odd char is found put that in respective set
• then find if any char of set 1 is present in set2 then take that char because that will produce the longest palindrome
if not present then take the smallest from the first char of set1 and of set2 and put it in ans string and then simply
``````#include<bits/stdc++.h>
using namespace std;

string solve(string &str1,string &str2){
unordered_map<char,int> mp1,mp2;
multiset<char> ms;
set<char> st1,st2;

for(auto i : str1) mp1[i]++;
for(auto i : str2) mp2[i]++;

for(auto [key,val] : mp1){
if(val%2) st1.insert(key);
val /= 2;
while(val--) ms.insert(key);
}

for(auto [key,val] : mp2){
if(val%2) st2.insert(key);
val /= 2;
while(val--) ms.insert(key);
}

bool flag = true;
for(auto ele : st1){
if(st2.count(ele)){
flag = false;
ms.insert(ele);
}
}

string ans;
for(auto ch : ms) ans += ch;

string rev = ans;
reverse(rev.begin(),rev.end());

if(flag and (st1.size() or st2.size())){
char ch = '~';
if(st1.size()) ch = min(ch,*st1.begin());
if(st2.size()) ch = min(ch,*st2.begin());
ans += ch;
}

ans += rev;

return ans;
}

int main(){
string str1,str2; cin>>str1>>str2;
cout<<solve(str1,str2)<<endl;
}``````
by Expert (46,090 points)