## JavaScript (ES6), <s>76</s> 73 Bytes ##

    g=
    (x,y)=>x.length>y.length?g(y,x):[...x].map(c=>y=y.replace(c,''))&&x+'_'+y
    ;
Simple JS solution to kick things off. 
I will try to golf this down more during the day.