It is mathematically possbile do what they are doing securely to store passwords in a manner that would enable that feature but would not have the old password stored in plaintext. But just because it is mathematically possible, does not mean that it is likely.
At Eurocrypt 2004 Michael Freedman, Kobbi Nissim, and Benny Pinkas presented a paper that explicitly addressed how to efficiently find the intersection of two sets without revealing the contents of either set (other than the intersection) to anyone who didn't have it before. It is also possible to find an estimate of the size of the intersection without even revealing (much about) the intersection itself.
Now that was in 2004 (and was based on previously work). So there have been improvements since then in this and related algorithms. So there are known techniques for finding out how many characters are common to two sets without revealing the contents of either set. (In the case you are asking about, it is only one set, the old password, that needs to be concealed as the system is given the full new password.)
If we are talking about overlap of sequences of four characters (instead of just characters in both passwords), then a reasonably secure way of doing this is with a Bloom Filter. A Bloom Filter is a special sort of hash table. Each four character substring of the original password could be added to the Bloom filter when that password given to the service and then all four character substrings of the new password can be looked up in the Bloom filter.
Note that Bloom filters are designed for when there are lots of members of the set and are probabilistic. They can give false positives.
The obvious answer is sadly correct
I would be astounded if the site in question is using homomorphic encryption or even Bloom filters. They are almost certainly doing it a manner in which the operators of the site (and anyone who breaches them) have access to the plaintext passwords.