One way to do this is to store a much weaker hash of the password and require some minimum difference in that hash, e.g. add all the character codes together, a

One way to do this is to store a much weaker hash of the password and require some minimum difference in that hash, e.g. add all the character codes together, and reject a new password if its sum doesn't differ by at least 50.