Most systems that allow you to change your password require the current password as a verification. This means the software performing the validation of the new password also has access to your old password and could perform a comparison of the two to see how many characters differ or the overall edit distance.
If only the new password is available, it’s still possible to perform this analysis against older password hashes by simply manipulating the new password and checking if it validates against the old hashes. Possible transformations are replacing any numbers with other digits, e.g. “foobar2” would check “foobar1” through “foobar9”.