Somebody already mentioned using chop for high performance traversal of such strings. In this case, the requirement can just as well traverse backwards through the big string. I see no need for pattern-matching - just store the last positions and strings accumulated for each letter in a hash of hash and the current winning string in a scalar and just chop back through, updating the positions, trial strings and current winning string as appropriate.