Is there any way to check that with non-plain-text password?

Actually it can be trivial as long as you can require the user to re-type the current password when entering a new password; check hash first, then check edit distance with the entered "current password" (and, of course, promptly throw it away once you know the edit distance.)

Ohh. I guess that's what Windows does when a user wants to change their own password in the domain.

It does more than that, it keeps a hashed password history (which used to be in the user attr ntPasswdHistory, but is now "somewhere secret" afaik) according to the value of ms-DS-Password-History-Length attribute. OpenLDAP keeps these (ppolicy overlay) in the user object.

So, it can hash any proposed password and compare the history to make it's not been seen $recently (as an exact match, since it's comparing hashes).

It could also perform some minor permutations of any new password, and do the same history check to make sure you're not just changing the first or last character or digit. I don't know if it does this, but it could.

Unless they ask you for your current password as part of the password change flow.

No it doesn't. Shows you how complicated all this is and how the un-initiated (including me) should learn to not give their two cents.

When you do the password change it asks you for the old one, that's how it knows.

So it asks for old + new, checks old is correct against the hash, and then compares old + new likeness.

So it all happens in memory.