If they’re using some special hash algorithm that retains most of the information of the original password and allows them to determine that “password1” and “password2” are similar and “blahblah7” is not, their approach is hopelessly broken too.
Technically you could tokenize and dictionary plus edit distance check the password in the client if you have the plaintext, or use malleable hashing. Check entropy while at it. Of course that will not stop a determined policy ignorant.
Requiring a plaintext password storage somewhere is an instant regulatory fail in ISO 27002 and PCI DSS standard. You can technically store the passwords encrypted, but attacker is liable to steal your salt/key, and protecting the passwords in transit strictly requires strong PKI. We know users cannot determine that anyway and get phished/MITMed.
Plus it's kind of mean. If your users are determined to ignore your policy, maybe it's a bad policy or you need to tell them to stop doing that.
Checking for x latest passwords requires just storing their hashes.
If they’re using some special hash algorithm that retains most of the information of the original password and allows them to determine that “password1” and “password2” are similar and “blahblah7” is not, their approach is hopelessly broken too.