4

Java, 14307139 bytes
Hamlet - 601,218
Genesis - 13,705,921
The idea here is to do all the work upfront, by making a character->character map. Then you can just loop through and grab the shortest strings.
A bit of an exception has to be made for numerals, so I check for them in the main loop. ...