Difficulty: Medium Category: String Matching & Combinatorics Original Problem
Problem Summary
You have a vocabulary of N distinct words, each of length L, using only the letters {m, e, t, a}. Your friend wrote Q misspelled words, also of length L using the same alphabet.
For each misspelled word, count how many vocabulary words differ from it at exactly 2 positions. Sum all counts across all Q queries.
Example:
Vocabulary: [“meta”, “meet”, “mete”]
Query word: “mate”
“meta”: differs at positions 1 (a vs e) and 3 (t vs e) → 2 differences ✓
“meet”: differs at positions 1 (a vs e) → 1 difference ✗
“mete”: differs at positions 1 (a vs e), 2 (t vs e), 3 (e vs t) → 3 differences ✗
Count: 1
Understanding the Problem
Hamming Distance
The “differ at exactly 2 positions” concept is Hamming distance = 2. The Hamming distance between two strings is the number of positions where their characters differ.
