Sherlock and Anagrams

Problem Statement

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

Input Format

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

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

Output Format

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

Sample Input

2
abba
abcd

Sample Output

4
0

Explanation

Let's say S[i,j] denotes the substring Si,Si+1,⋯,Sj.

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

testcase 2: 
No anagrammatic pairs.

import java.io.*;
import java.util.*;

public class Solution {

    public static void main(String[] args) {
// TODO Auto-generated method stub
   Scanner in = new Scanner(System.in);
       int N = in.nextInt();
       Map<String, Integer> frequency = new HashMap<String, Integer>();
       while(N > 0){
        frequency.clear();
           String entry = in.next();
           int pairCount = 0;
           for(int i = 0; i < entry.length(); i++){
               for(int j = i+1; j <= entry.length(); j++){
                char[] keySeq = entry.substring(i, j).toCharArray();
                Arrays.sort(keySeq);
                String key = new String(keySeq);
                if(frequency.containsKey(key)){
                frequency.put(key, frequency.get(key)+1);
                }else{
                frequency.put(key, 1);
                }
               }
           }
           int sum = 0;
           Set<String> keys = frequency.keySet();
           for(String key : keys){
            sum += (frequency.get(key)*(frequency.get(key)-1))/2;
           }
           System.out.println(sum);
           N--;
       }
}
}