Hackerrank Strings Solution : Sherlock and Anagrams.py

Hackerrank Strings Solution : Sherlock and Anagrams.py

Problem Statement:

Given a string S$S$, find the number of "unordered anagrammatic pairs" of substrings.

Input Format 
First line contains T$T$, the number of testcases. Each testcase consists of string S$S$ in one line.

Constraints 
1≤T≤10$1\le T\le 10$ 
2≤length(S)≤100$2\le length(S)\le 100$ 
String S$S$ contains only the lowercase letters of the English alphabet.

Output Format 
For each testcase, print the required answer in one line.

Sample Input#00

2
abba
abcd

Sample Output#00

4
0

Sample Input#01

5
ifailuhkqq
hucpoltgty
ovarjsnrbf
pvmupwjjjf
iwwhrlkpek

Sample Output#01

3
2
2
6
3

Explanation

Sample00 
Let's say S[i,j]$S[i,j]$ denotes the substring Si,Si+1,⋯,Sj$S_i,S_{i+1},\cdots ,S_j$.

testcase 1: 
For S=abba, anagrammatic pairs are: {S[1,1],S[4,4]}$\{S[1,1],S[4,4]\}$, {S[1,2],S[3,4]}$\{S[1,2],S[3,4]\}$, {S[2,2],S[3,3]}$\{S[2,2],S[3,3]\}$and {S[1,3],S[2,4]}$\{S[1,3],S[2,4]\}$.

testcase 2: 
No anagrammatic pairs.

Sample01 
Left as an exercise to you.

Language: Python

Solution:

import collections
n = input()
while(n>0):
    n-=1
    k = raw_input()
    dictionary = collections.defaultdict(int)
    lst = list(k)
    length = len(k)
    for i in range(0,length):
        for j in range(1,length-i+1):
            sam = lst[i:i+j]
            sam = sorted(sam)
            dictionary[''.join(sam)] += 1
    ans = 0
    for value in dictionary.values():
        ans += (value*(value-1))/2
    print ans

Thanks for Visiting, Hope this helps you....