I like the ones that not only keep a history of your old passwords but will reject any password that is similar to any of your 30 previous passwords, which means they're storing either a plaintext or reversibly encrypted list of every password somewhere on the system. Talk about a goldmine for the hacker that dumps that database.
This doesn't seem practical at all. The combinatoral explosion would make the storage requirements impractical for everything but the absolutely most trivial cases like incrementing a number as the very last digit. Even in your simple example you're talking about storing 256 different hashes just to catch one possible mutation on a way too short password.
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.
Technical/pedantic answer: you can store a 'normalized' hashed form of the password, e.g. before hashing it, convert it to all lowercase, replace all digits with 0, sort the characters, … and then do the same to the new password before hashing it, so a whole bunch of stuff will compare "equal".
Practical/actual answer: this is stupid either way.
Something like that could probably be implemented by storing multiple hash of some automatically modified version of the password. For example, if your password is "PassWorD" they can additionally store the hash of the lowercase version of the password. So if you change it from "PassWorD" to "paSswOrd", they will see it has the same lowercase hash than the previous one without knowing it.