1228. Key Collision Count
A tiny hash table stores words using the hash h(w) = (sum over i of (w[i] - 'a' + 1) * base^i) mod modulus, where i is the 0-based position in the word, so 'a' weighs 1 and 'z' weighs 26. Compute it with modular arithmetic at every step, since base^i gets huge.
A collision is a pair of indices i < j with h(words[i]) == h(words[j]) but words[i] != words[j]. Equal words are not collisions. Return the number of collisions in words as a 64-bit integer.
Hash every word once, then count pairs per hash value with a map and remove the identical-word pairs. Time is O(total characters), space O(n).
Example 1
- Input:
- words = ["a","b","c"], base = 5, modulus = 2
- Output:
- 1
- Explanation:
The hashes are 1, 2 and 3 modulo 2, i.e. 1, 0, 1, so "a" and "c" collide: 1 collision.
Example 2
- Input:
- words = ["aa","aa"], base = 2, modulus = 7
- Output:
- 0
- Explanation:
The words are identical, so equal hashes do not count and the answer is 0.
Example 3
- Input:
- words = ["a","a","d","b"], base = 3, modulus = 3
- Output:
- 2
- Explanation:
"a", "a" and "d" all hash to 1; the 3 pairs minus the identical pair (a, a) leave 2 collisions.
Constraints
1 ≤ words.length ≤ 1000
1 ≤ words[i].length ≤ 20
words[i] consists of lowercase English letters.
2 ≤ base ≤ 1000
1 ≤ modulus ≤ 104
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(L)
- Space
- O(n)