Message on Whatsapp 8879355057 for DSA(OA + Interview) + Fullstack Dev Training + 1-1 Personalized Mentoring to get 10+LPA Job
0 like 0 dislike
2,780 views
in Online Assessments by Expert (46,090 points) | 2,780 views

3 Answers

0 like 0 dislike
Best answer

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'

image
image

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)