Io avevo pensato a questa soluzione, solo che non so come implementarla ricorsivamente:

1) Confronto ciascun elemento della stringa più lunga con tutti gli elementi della stringa più corta. Se trovo l'elemento interrompo la ricerca e lo copio nella stringa risultato. Altrimenti continuo la ricerca e se non trovo nessun elemento della stringa corta corrispondente all'elemento della stringa lunga che sto analizzando, allora lo copio nella stringa risultato.

2) Una volta completata la stringa lunga, passo alla stringa corta e confronto ciascun elemento della corta con tutti gli elementi della stringa risultato. Se trovo l'elemento della corta nella stringa risultato allora non copio nulla, altrimenti copio il carattere della stringa corta nella stringa risultato.