Question

Atlassian | OA | SDE1 | Coding Questions and Solutions | 2022 | Set-15

Answer 1

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'

Answer 2

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]

Answer 3

• 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;
}