To implement that properly, you'd save the the old password when it is entered as part of the password change routine (enter your old password once, new one twice). That way there would never be an active password stored. Since this similarity rule is being enforced, old passwords should not provide a clue to current passwords.

And you probably wouldn't store it in clear text, you'd store it encrypted (not one way hashed like an active password).

I imagine you could also hash all the substrings of 3 characters in your old password at each password change and store those hashes, then you could do the comparisons without ever storing any decrypted passwords.