And now for something a little different...

This method certainly won't win any speed prizes. And I'm not even sure why I did it -- except just to see it work. It relies on the fact that any composite number can be factored but one way into its constituent primes. We begin by assigning each letter of the alphabet a unique prime number. Each unordered string of letters -- a set, really -- can be represented as the product of the primes those letters represent. The difference between two strings, then, will be the quotient of the first product divided by the second, factored into its constituent primes and converted back to letters. This is assuming that the numbers evenly divide, i.e. that the remainder of the division is zero. If not, the string difference is undefined, because it means the second string has letters in it not contained in the first.

The following program illustrates the technique:

use Math::BigInt;
@Primes = (2,3,5,7,11,13,17,19,23,29,31,37,41,
    43,47,53,59,61,67,71,73,79,83,89,97,101);
@AsciiPrimes = ((0) x 65, @Primes, (0) x 6, @Primes, (0) x 133);

print StringDif('abcdgoldfish', 'flash'),"\n";
print StringDif('lmnogoldfish', 'dish'),"\n";
print StringDif('osar', 'oar'),"\n";

sub StringDif {
    my ($StrA, $StrB) = @_;
    my $A = Math::BigInt->new(1);
    my $B = Math::BigInt->new(1);
    my $Quot, $Rem, $NewQuot, $ReturnStr;
    foreach (unpack 'C*', $StrA) {$A *= $AsciiPrimes[$_]}
    foreach (unpack 'C*', $StrB) {$B *= $AsciiPrimes[$_]}
    if ($A eq '+0' or $B eq '+0') {
        warn "Non-letter in string"; return undef
    }
    ($Quot, $Rem) = Math::BigInt->new($A)->bdiv($B);
    return undef unless $Rem eq '+0';
    $ReturnStr = '';
    foreach('a'..'z') {
        do {
            ($NewQuot, $Rem) = Math::BigInt->new($Quot)
                ->bdiv($AsciiPrimes[ord $_]);
            if ($Rem eq '+0') {
                $ReturnStr .= $_;
                $Quot = $NewQuot
            }
        } while $Rem eq '+0' 
    }
    return $ReturnStr
}
[download]

Note that, due to the use of Math::BigInt, strings can be as long as you like. Also, even though the input strings don't have to be sorted, the output string will be.