Anagrams (LeetCode HashMap)

Question: Given an array of strings, return all groups of strings that are anagrams.
Note: All inputs will be in lower-case.

Idea: Sort each of the string in O(n) time. Then scan the sorted strings one by one and use a HashMap<sorted string, ArrayList<original string index>> to check whether there are anagrams. If the ArrayList<original string index> has a size over 1, output.

Time: O(n^2) Space: O(n)

Code:

 public class Solution {  
   public List<String> anagrams(String[] strs) {  
     List<String> result=new ArrayList<String>();  
     if(strs==null||strs.length==0)  
     {  
       return result;  
     }  
     HashMap<String,ArrayList<Integer>> map=new HashMap<String,ArrayList<Integer>>();  
     for(int i=0;i<strs.length;i++)  
     {  
       String sorted=specialSort(strs[i]);  
       if(map.containsKey(sorted))  
       {  
         map.get(sorted).add(i);  
       }  
       else  
       {  
         ArrayList<Integer> tmp=new ArrayList<Integer>();  
         tmp.add(i);  
         map.put(sorted,tmp);  
       }  
     }  
     for(String s:map.keySet())  
     {  
       if(map.get(s).size()>=2)  
       {  
         for(int i:map.get(s))  
         {  
           result.add(strs[i]);  
         }  
       }  
     }  
     return result;  
   }  
   public String specialSort(String s)  
   {  
     HashMap<Character,Integer> map=new HashMap<Character,Integer>();  
     for(char c:s.toCharArray())  
     {  
       if(map.containsKey(c))  
       {  
         map.put(c,map.get(c)+1);  
       }  
       else  
       {  
         map.put(c,1);  
       }  
     }  
     StringBuilder builder=new StringBuilder();  
     for(char c='a';c<='z';c++)  
     {  
       if(map.containsKey(c))  
       {  
         int counter=0;  
         while(counter<map.get(c))  
         {  
           builder.append(c);  
           counter+=1;  
         }  
       }  
     }  
     return builder.toString();  
   }  
 }