Comment by medvezhenok

It probably requires some sort of decreased security (if the password hash is truly slow & secure, it would be hard to enforce dissimilarity); but there might be other methods that leak less than cleartext (like salting and storing hashes of overlapping/separate n-grams from the previous password and checking for number of similar n-grams; etc). Or as another commenter suggested checking all passwords within edit distance 1 (though if you can do that, your password hashing algorithm is likely too fast).