1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – D.W. Mar 15 '17 at 17:50
  • $\begingroup$ 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. $\endgroup$ – Rockstar5645 Mar 16 '17 at 15:34
  • $\begingroup$ Please edit the question to incorporate the information into the question. We want questions to be self-contained, so people don't have to read the comments to understand what you are asking -- comments exist only to help you improve your question, and comments can disappear at any time. Also note that the usual rule is that we prefer that you ask only one question per post. You can ask one question, then absorb the answer, and ask the next question separately. $\endgroup$ – D.W. Mar 16 '17 at 16:20
  • $\begingroup$ For why you add that many pairs, what analysis have you done? How many pairs do you think will be added? Try working through some examples, then show your analysis and what you think the expression should be and why, before asking us to explain why that is the right number. You might find that you're able to answer the question on your own; or, showing your work might enable us to help point out your misconception or where you want wrong. $\endgroup$ – D.W. Mar 16 '17 at 16:20
  • $\begingroup$ okay, let me try analysing it myself. $\endgroup$ – Rockstar5645 Mar 17 '17 at 15:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.