## Hackerrank - Sherlock and Anagrams Solution

Two strings are *anagrams* of each other if the letters of one string can be rearranged to form the other string. Given a string, find the number of pairs of substrings of the string that are anagrams of each other.

For example , the list of all anagrammatic pairs is at positions respectively.

**Function Description**

Complete the function *sherlockAndAnagrams* in the editor below. It must return an integer that represents the number of anagrammatic pairs of substrings in .

sherlockAndAnagrams has the following parameter(s):

*s*: a string .

**Input Format**

The first line contains an integer , the number of queries.

Each of the next lines contains a string to analyze.

**Constraints**

String contains only lowercase letters ascii[a-z].

**Output Format**

For each query, return the number of unordered anagrammatic pairs.

**Sample Input 0**

```
2
abba
abcd
```

**Sample Output 0**

```
4
0
```

**Explanation 0**

The list of all anagrammatic pairs is and at positions and respectively.

No anagrammatic pairs exist in the second query as no character repeats.

**Sample Input 1**

```
2
ifailuhkqq
kkkk
```

**Sample Output 1**

```
3
10
```

**Explanation 1**

For the first query, we have anagram pairs and at positions and respectively.

For the second query:

There are 6 anagrams of the form at positions and .

There are 3 anagrams of the form at positions and .

There is 1 anagram of the form at position .

**Sample Input 2**

```
1
cdcd
```

**Sample Output 2**

`5`

**Explanation 2**

There are two anagrammatic pairs of length : and .

There are three anagrammatic pairs of length : at positions respectively.

### Solution in Python

```
from collections import Counter
def sherlockAndAnagrams(s):
count = Counter(("".join(sorted(s[j:j+i])) for i in range(1,len(s)) for j in range(0,len(s)-i+1) ))
return sum(sum(range(i)) for i in count.values())
for _ in range(int(input())):
s = input()
print(sherlockAndAnagrams(s))
```

*Answer breakdown*

Let our string be s = "ifailuhkqq"

First we find all possible substrings of s.

```
for i in range(1,len(s)):
for j in range(0,len(s)-i+1):
print(s[j:j+i],end=", ")
```

We will get the following output:

`i, f, a, i, l, u, h, k, q, q, if, fa, ai, il, lu, uh, hk, kq, qq, ifa, fai, ail, ilu, luh, uhk, hkq, kqq, ifai, fail, ailu, iluh, luhk, uhkq, hkqq, ifail, failu, ailuh, iluhk, luhkq, uhkqq, ifailu, failuh, ailuhk, iluhkq, luhkqq, ifailuh, failuhk, ailuhkq, iluhkqq, ifailuhk, failuhkq, ailuhkqq, ifailuhkq, failuhkqq, `

Above is all the possible substrings of our string s.

We have to find anagram substrings, which means order of our string doesn't matter. Therefore we will sort each of our substring so that we group substrings having the same characters.

Example: ifa and fai are anagrams. After sorting, both will become afi after sorting.

```
for i in range(1,len(s)):
for j in range(0,len(s)-i+1):
print("".join(sorted(s[j:j+i])),end=", ")
```

Output

`i, f, a, i, l, u, h, k, q, q, fi, af, ai, il, lu, hu, hk, kq, qq, afi, afi, ail, ilu, hlu, hku, hkq, kqq, afii, afil, ailu, hilu, hklu, hkqu, hkqq, afiil, afilu, ahilu, hiklu, hklqu, hkqqu, afiilu, afhilu, ahiklu, hiklqu, hklqqu, afhiilu, afhiklu, ahiklqu, hiklqqu, afhiiklu, afhiklqu, ahiklqqu, afhiiklqu, afhiklqqu, `

Let arr = list of all possible substrings

Now we will use Counter to group and count all the sorted substrings.

```
>>> print(Counter(arr))
Counter({'i': 2, 'q': 2, 'afi': 2, 'f': 1, 'a': 1, 'l': 1, 'u': 1, 'h': 1, 'k': 1, 'fi': 1, 'af': 1, 'ai': 1, 'il': 1, 'lu': 1, 'hu': 1, 'hk': 1, 'kq': 1, 'qq': 1, 'ail': 1, 'ilu': 1, 'hlu': 1, 'hku': 1, 'hkq': 1, 'kqq': 1, 'afii': 1, 'afil': 1, 'ailu': 1, 'hilu': 1, 'hklu': 1, 'hkqu': 1, 'hkqq': 1, 'afiil': 1, 'afilu': 1, 'ahilu': 1, 'hiklu': 1, 'hklqu': 1, 'hkqqu': 1, 'afiilu': 1, 'afhilu': 1, 'ahiklu': 1, 'hiklqu': 1, 'hklqqu': 1, 'afhiilu': 1, 'afhiklu': 1, 'ahiklqu': 1, 'hiklqqu': 1, 'afhiiklu': 1, 'afhiklqu': 1, 'ahiklqqu': 1, 'afhiiklqu': 1, 'afhiklqqu': 1})
```

Great!, now we have got the count of our every possible sorted substrings. All the substrings that have atleast 2 counts are the substrings which can make an anagram pair.

```
>>> count = {k:v for k,v in Counter(arr).items() if v>1}
>>> count
{'i': 2, 'q': 2, 'afi': 2}
```

So "i',"q" and "afi" are the substrings which appears more than once

Before moving to the last part. I would like to tell you that. If a substring appears k times, then the total possible anagrams of that substring will be 1+2+3+......+(k-1)

Example in string "kkkk".

Total possible anagrams of ["k","k"] will be 1+2+3 = 6, as there are 4 substrings of "k" in "kkkk".

Total possible anagrams of "kk" will be 1+2 = 3, as there are 3 substrings of "kk" in "kkkk".

Total possible anagrams of "kkk" will be 1 , as there are 2 substrings of "kkk" in "kkkk".

Total anagrams of the string "kkkk" = 6+3+1 = 10.

Notice that 1+2+3 ,1+2, 1 can be written as sum(range(4)), sum(range(3)), sum(range(2)) i.e sum(range(countOfString))

*Back to our original problem.*

Final part

```
>>> count.values()
[2,2,2]
```

Just add the range sum of each of these counts.

```
total = 0
for i in count.values():
total += sum(range(i))
print(total)
```

Output: 3

In short it can be written as

```
>>> sum(sum(i) for i in count.values())
3
```

That's it. If you have any doubt feel free to leave a comment below.