Group Anagrams

Here is the problem: https://leetcode.com/problems/group-anagrams
My solution: Prime Decomposition | Simple Clean C++ Faster than 98%

Explanation

Here the prime number is used to avoid collisions. Let's discuss this step by step.

• Lets say [a = 1, b = 2, c = 3, d = 4, e = 5, f = 6]. Now "af" and "bc" will generate same key. Now we might use some other values to decrease the probability of collision. But the probability still exists.
• The problem here is for any number we have more than one set of factors. For example, 42 has factors 2, 3, 6, 7, 14, 21 and 42. Which means there are more than one ways to get 42. Such as (2 x 21), (3 x 14), (6 x 7), and even (1 x 42). Which is a bad thing for us. There should only be one way to generate 42. Similarly "af" and "bc" should each generate an unique key instead of both being 6 Luckily for us, primes numbers has this uniqueness. Any number can be written as multiplication of 2 or more prime number in only one unique way. Video explanation: youtu.be/5qERjjlEVe4
• For example 3 x 14 = 3 x 2 x 7 = 42, here (3, 2, 7) are prime numbers. There other no other way to generate 42 other than these three prime numbers. (1, 4, 6, 14, 42) are not prime numbers. So we can't use them.
• Now we only need to convert the charcters into prime numbers. Since we only have 26 characters we will assign a prime number to each one of them.
• int primes[26] =[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101];
  Here for "ned" the key will be
  = primes[110 - 97] x primes[101 - 97] x primes[100 - 97]
  = primes[13] x primes[4] x primes[3]
  = 43 x 11 x 7 ( key = key * this->primes[ch - 97] )
  = 3311 ( no other set of characters will generate this result )

Lastly, I used key %= this->modulo; To prevent overflow. For example, character a is mapped to prime number 2. Here for "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" , the result will be a massive number (2^99). To prevent overflow we decrease it with 1,000,000,007(1e9 + 7) which is also a prime number and just take the remainder.