sub c {my(@a,%h,$i)=split//,pop;my$s=pop;$s=~s!(.)!$h{$1}||=$a[$i++]!g
+e;$s}
[download]

Update: got rid of one character by using substr:

sub c {my($a,%h,$i)=pop;my$s=pop;$s=~s!(.)!$h{$1}||=substr$a,$i++,1!ge
+;$s}
[download]

Update 2: if you don't need strict:

sub c {($s,$a)=@_;my(%h,$i);$s=~s!(.)!$h{$1}||=substr$a,$i++,1!ge;$s}
[download]

Update 3: Oh, and the reason I'm still initializing %h and $i is so that the sub will work on repeated invocations. If we don't *have* to do that, this will do:

sub c {($s,$a)=@_;$s=~s!(.)!$h{$1}||=substr$a,$i++,1!ge;$s}
[download]

Update 4: Use $_:

sub c {($_,$a)=@_;s!(.)!$h{$1}||=substr$a,$i++,1!ge;$_}
[download]

Update 5: Okay, so none of these actually *work* per the spec. Thanks, tilly. :)