There are locality-preserving hash functions. The typical case is rather non-cryptographic, but there are ways to trade optimal locality parameters against cryp

There are locality-preserving hash functions. The typical case is rather non-cryptographic, but there are ways to trade optimal locality parameters against cryptographic security. Also one could use a bloom filter to keep track of the passwords that were used, and have it alert if the to-be-set password can be permutated with some given rules into a password the bloom filter matches. As soon as it matches, you can then do an expensive check against the old salted password to weed out false-positives.