Ah, I see. (Also didn't realize that String::Approx doesn't use regexes)
So this is crazy, but it just might work: stick each letter of one string into one array, then each letter of the other string into the other array. Then use List::Compare to figure out how the two strings are different.
List::Compare is my favorite hammer these days. =)