Sherlock and Anagrams

Given a string , find the number of "unordered anagrammatic pairs" of substrings.
Input Format
First line contains , the number of testcases. Each testcase consists of string in one line.
Constraints


String 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 denotes the substring .
testcase 1:
For S=abba, anagrammatic pairs are: , , and .
testcase 2:
No anagrammatic pairs.
Sample01
Left as an exercise to you.

Analysis

this seems complex, I have no optimized way to work it out. brute force way is working and basic idea is as follow:

1. categorize the substrings into categories according to their length, because anagram is between strings with same length(same length, same number of characters). single character is also a substring.

2. within each category, calculate the number of anagram pairs

3. sum numbers from all categories.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65

import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; public class Solution { public static void main(String[] args) { /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */ Scanner in = new Scanner(System.in); int n = in.nextInt(); String[] ss = new String[n]; for(int i=0;i<n;i++){ checkAnagramPairs(in.next()); } } /** two steps: 1.categorize the substrings, same length strings are put together 2. figure out num of pairs in each category 3. sum 2 */ private static void checkAnagramPairs(String s){ if(s==null||s.length()==1)System.out.println(0); Map<Integer,List<String>> stats = new HashMap<Integer,List<String>>(); for(int i=0;i<s.length();i++){ for(int j=i+1;j<=s.length();j++){ if(stats.get(j-i)==null){ List<String> l = new ArrayList<String>(); l.add(s.substring(i,j)); stats.put(j-i,l); }else{ stats.get(j-i).add(s.substring(i,j)); } } } int ttl = 0; for(Map.Entry<Integer,List<String>> e:stats.entrySet()){ ttl+=getNumOfAnagramPairs(e.getValue()); } System.out.println(ttl); } private static int getNumOfAnagramPairs(List<String> l){ int ttl = 0; for(int i=0;i<l.size();i++){ for(int j=i+1;j<l.size();j++){ if(isAnagramPair(l.get(i),l.get(j))){ ttl++; } } } return ttl; } private static boolean isAnagramPair(String s1,String s2){ char[] c1 = s1.toCharArray(); Arrays.sort(c1); char[] c2 = s2.toCharArray(); Arrays.sort(c2); s1 = new String(c1); s2 = new String(c2); return s1.equals(s2); } }