# most efficient way to compute number of anagrams of a string

This is a question from Hackerrank.

Given a string S, find the number of "unordered anagrammatic pairs" of substrings. In other words, find the number of unordered pairs of substrings of S that are anagrams of each other.

Two strings are anagrams of each other if the letters of one string can be rearranged to form the other string.

Here is an example:

For S = "abba" , anagrammatic pairs are $$\{ S[1,1], S[4,4] \},\;\; \{ S[1,2], S[3,4] \},\;\; \{ S[1,3], S[2,4] \},\;\; \{ S[2,2], S[3,3] \}$$

where the $[i, j]$ represents the starting and ending index of each substring (indexing starts at 1)

My solution got accepted but I think it's really slow (I don't know how to analyse the time complexity of it). So I looked in the editorial, and I didn't understand the approach used by the problem setter

Editorial:

How to check anagrams
We need to check if string S1 and S2 are anagrams, we first build frequency table where frequency[i] stores the frequency of character i+a. If two strings have same frequency table they are anagrams.

Approach 1
Traverse over all $O(N \times N)$ substrings and for each substring in $O(N)$ build the frequency table and store after hashing. For each $key$ in hashtable, we add $\frac{value \times (value-1)}{2}$ pairs to answer. A factor of $26$ arrives in complexity due to hashing of frequency tables. Overall complexity: $O(N^3 \times 26)$

Approach 2
Starting for $i=1$ to $N$, we dynamically build frequency for substring $S[i, j]$ where $j$ ranges from $i$ to $N$. So, overall complexity here would be $O(N^2 \times 26)$.

Can someone explain both approach 1 and 2?

• What specifically don't you understand, and what parts do you understand? Have you tried working through some small examples by hand, to see what each approach is doing? – D.W. Mar 15 '17 at 17:50
• I don't really understand how to "store after hashing." Or why we add value*(value-1)/2 pairs to the answer for each key in hashtable. Or how to "dynamically build frequency for substrings s[i, j]..." in approach 2. I only understand how to create a normal frequency table, the maps each character to number of occurrences. – Rockstar5645 Mar 16 '17 at 15:34