Ask HN: How does Facebook detect slight misspelling of password?

I just tried logging into FB and I inadvertently misspelled my password. FB detected this and told me that my password was slightly off (this isn't the exact error message but is representative).

How do they know? I use BCrypt on my sites and I wonder how such a message can be generated if you haven't stored the plain text password? One way could be to also store some other hash that makes computing the edit distance easy but wouldn't that negate the problem BCrypt solves in the first place (namely making it hard to brute force the correct password)?