Not necessarily, I forgot to mention that when changing your password through their UI you still have to enter your old password. So it's safe to assume that the string comparison is made at form submission. For history rule I don't want to imagine it being implemented otherwise.
Does this sort of rule imply that they are saving passwords whole (either plaintext or encrypted, as opposed to hashed)? I can understand "can't match your last N passwords" cause that's just saving old hash entries. But editdistance(old, new) < 3 implies you know the string value somewhere.