$string =~ s/(a|b)/$map{ $1 }/g;

##</code><code>##

$pattern = join '|', map quotemeta, keys %map;
$string =~ s/($pattern)/$map{ $1 }/go;  # /o only if the pattern never changes

##</code><code>##

use Regex::PreSuf;
my $pattern= presuf(keys %map);
$string =~ s/($pattern)/$map{ $1 }/go;

##</code><code>##

$pattern = join '|', map quotemeta, sort { length($b) <=> length($a) } keys %map;

##</code><code>##

$pattern = join '|', map quotemeta, sort { $b cmp $a } keys %map;