Comment by andrewaylett

You can store a normalised form -- so if the password is `PaSsWoRd` and the user tries to change it to `pA55wOrD`, a normalisation that lower-cases, turns 1 and i into l, turns 2 and 5 into s, and turns 4 into a, would normalise both to `password`.

Or if you want a slightly more convoluted mechanism, when someone changes their password you have both in plain-text and you can take a copy of the old password at that point -- after all, it's not being used as a password any more! For bonus fun, submit all previous passwords to pwned passwords. Password reuse makes this a bad idea in general, specific policies attempting to mandate it will not be an issue notwithstanding.