Spell Checker

You are given a dictionary that maps words to their frequencies, and a query that might be misspelled. Return up to maxSuggestions real words that are within maxDistance edit operations of the query, ranked by edit distance first (fewer edits wins) and frequency second (more common wins among ties).

"Edit distance" here is the Levenshtein distance, which counts the minimum number of single-character insertions, deletions, or substitutions needed to transform one string into another.

query: "helo"    → ["help", "hello", "he", "her", "here"]
query: "hourse"  → ["house", "horse", "hose"]
query: "thier"   → ["the", "this", "they", "her", "there"]

Two knobs set the budget. maxDistance defaults to 2, which is the practical upper bound for single-word typos. maxSuggestions caps the result length and defaults to 5.

Tiebreak is worth pausing on. At the same distance, you want to surface the more common word first, because a user's misspelling is much more likely to have targeted a frequent word than a rare one. "teh" should suggest "the" over "he" even though both are within 2 edits.

The natural read of the problem is direct. For each candidate word in the dictionary, compute the full edit distance against the query. Keep candidates whose distance is within maxDistance. Sort by (distance ascending, frequency descending). Return the top maxSuggestions words.