TypeScript Solution 49ms Runtime Beats 100% Explained with comments
\n# Intuition\nUsing prime numbers, one can come up with a hashing function to create an integer that uniquely identifies each set of characters, irrespective o
![valid anagram.PNG](https://assets.leetcode.com/users/images/ba2bdf32-6bd0-40cf-b894-6a9acbe1365c_1685454289.0464385.png)\n# Intuition\nUsing prime numbers, one can come up with a hashing function to create an integer that uniquely identifies each set of characters, irrespective of their order, then compare the two integers to validate the presence of two anagrams. \n# Approach\n1. A classic approach would be to use a hashmap to calculate and store each character\'s occurence in both strings, and compare the values to conclude if the two strings are anagrams.\n2. What I prefer to do is to leverage Math and hashing functions in order to create a faster algorithm that uses one loop instead of two when using hashmaps.\n3. In order to implement such an algorithm, we start by creating an array of the first 26 prime numbers, which we can later map to specific letters according to their ASCII code. The logic that makes this method valid is as follows:\n> Any number that is a product of several prime numbers, can only be recreated by using only those specific prime numbers, with respect to the number of times each one is used.\n4. You might be starting to understand what we\'re getting to. Our prime numbers array is indexed from `0 to 25`, which helps us map each character to a prime number using `s.charCodeAt(i) - 97`. For instance:\n> The letter \'a\' is equal to 97 in ASCII, so when we parse its ASCII value and substract 97 from it, we get 0 which allows us to map \'a\' as the prime number of the corresponding `s.charCodeAt(i) - 97` index, 2 in this case. \n5. And since the succeeding alphabet characters have their ASCII values in numerical order (\'b\' is 98, \'c\' is 99), this means that the letter \'b\' will map to 3, letter \'c\' will map to 5, etc...\n6. Having implemented this, we can now calculate a hash for every string, just by calculating the product of each letter\'s corresponding prime number `% 2^31 - 1`, which is done using the for loop.\n7. This way we will get a unique hash or number for each set of characters, and if two strings are anagrams, they will always have the same hash. So we return true if both hashes are equal, and false otherwise.\n# Complexity\n- Time complexity: O(N)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(26 + 4): 26 is the length of the prime array, and 2 is the number of extra variables used.\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\n// Declare MOD, hash1 & hash2 equal to 1, and the prime numbers array.\nfunction isAnagram(s: string, t: string, hash1 = 1, hash2 = 1, MOD = (Math.pow(2,31) - 1)): boolean {\n  const prime = [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]\n\n  for ( let i = 0; i < Math.max(s.length, t.length); i++ ) {    // Iterate over the longest string\n    let c1 = s.charCodeAt(i) - 97                               // Get ASCII value decremented by 97 and use it to map the\n    let c2 = t.charCodeAt(i) - 97                               // Letter with the value of the prime number at that index\n    hash1 = hash1*prime[c1] % MOD                               // Multiply the hash by the corresponding prime number\n    hash2 = hash2*prime[c2] % MOD                               \n  }\n  return hash1 === hash2                                        // Compare both hashes and return true if equal, or false otherwise\n};\n```\n\n\n# Second approach\n\nWe can also use addition instead of multiplication to create a unique hash, and this algorithm will perform as fast as the first one.\nNote the absence of a modulo, and the use of a different prime numbers array: an array of the first 26 prime numbers multiplied by their indeces starting from index 1.\n\n```\nfunction isAnagram(s: string, t: string, hash1 = 0, hash2 = 0): boolean {\n  const prime = [2, 6, 15, 28, 55, 78, 119, 152, 207, 290, 341, 444, 533, 602, 705, 848, 1003, 1098, 1273, 1420, 1533, 1738, 1909, 2136, 2425, 2626]\n\n  for ( let i = 0; i < Math.max(s.length, t.length); i++ ) {\n    hash1 += prime[s.charCodeAt(i) - 97]\n    hash2 += prime[t.charCodeAt(i) - 97]\n\n  }\n  return hash1 === hash2\n};\n```
['Math', 'String', 'Hash Function', 'TypeScript', 'JavaScript']