Count Anagrams - Leetcode Solution

Problem Statement:

Given an array of strings, return the count of all anagram pairs in the array.

An anagram of a string is another string that contains the same characters, but in a different order. For example, "abcd" and "dcba" are anagrams, as are "abba" and "bbaa".

Solution:

One approach to solve this problem is to classify anagrams together and count their occurrences. Two strings are anagrams if they have the same count of each character. We can use a hash table to store the count of characters in each string. For each string, we can count its characters and store it in a hash table. We can then check if there is another string in the array with the same hash table value. If there is, then it is an anagram pair. We can keep counting the number of anagram pairs that we find.

Here is the Python code implementation of the above approach:

def countAnagrams(strs):

# dictionary to store count of characters in each string
d = {}

# loop through each string in the array
for s in strs:
    
    # initialize an empty list to store the count of characters in the string
    chars = [0] * 26
    
    # count the occurrence of each character in the string
    for c in s:
        chars[ord(c) - ord('a')] += 1
    
    # convert the count list to a string and store it in the dictionary as a key, with its value as 0
    key = ' '.join(map(str, chars))
    d[key] = d.get(key, 0) + 1

# initialize the count of anagram pairs to 0
count = 0

# loop through the dictionary and count the pairs with the same count of characters
for k in d:
    n = d[k]
    count += n * (n - 1) // 2

return count

Here, we first initialize a dictionary d to store the count of characters in each string. We loop through each string s in strs and count the occurrence of each character in the string using a list chars. We then convert the count list to a string and store it in the dictionary as a key, with its value as 0. We then loop through the dictionary and count the number of anagram pairs using the formula n * (n - 1) // 2, where n is the count of strings with the same count of characters.

This solution has a time complexity of O(n * k), where n is the length of the array and k is the length of the longest string in the array. The space complexity is O(n * k), as we need to store the count of characters for each string in the dictionary.

1