You do not have to retain plaintext passwords to implement that. Just remember the past X hashes, generate all passwords within edit distance D of the new one, and compare the two lists.
Edit distance 3, even with "letter stays letter, digit stays digit, random additions and removals" will already give millions of variants, so this may be impractical, but impossible? No.
Oops, I should remember to check whether my replies are still useful after taking a break for a couple of hours. Finishing a once-original reply and hitting submit not always is the best idea. Apologies.
Edit distance 3, even with "letter stays letter, digit stays digit, random additions and removals" will already give millions of variants, so this may be impractical, but impossible? No.