# Acquiring indices for anagrams of an input string

I am working on an interview question from Amazon Software:

Design an algorithm to take a list of strings as well as a single input string, and return the indices of the list which are anagrams of the input string, disregarding special characters.

I was able to design the algorithm fine. What I did in psuedocode was:

1. Create an array character count of the single input string
2. For each string the list, construct the an array character count
3. Compare the character count of each string in list to single output string
4. If same, add it to a list that holds all the indexes of anagrams
5. Return that list of indices

Here is my implementation in Java (it works; I've tested it):

 public static List<Integer> indicesOfAnag(List<String> li, String comp){
List<Integer> allAnas = new ArrayList<Integer>();
int[] charCounts = generateCharCounts(comp);
int listLength = li.size();
for(int c=0;c<listLength; c++ ){
int[] charCountComp = generateCharCounts(li.get(c));
if(isEqualCounts(charCounts, charCountComp))
}
return allAnas;
}
private static boolean isEqualCounts(int[] counts1, int[] counts2){
for(int c=0;c<counts1.length;c++) {
if(counts1[c]!=counts2[c])
return false;
}
return true;
}
private static int[] generateCharCounts(String comp) {
int[] charCounts = new int[26];
int length = comp.length();
for(int c=0;c<length;c++) {
charCounts[Character.toLowerCase(comp.charAt(c)) - 'a'] ++;
}
return charCounts;
}


I think that this solution runs in $O(n)$ where n is the number of strings in the list (I'm not sure, so can someone verify?). What I am concerned about is the space complexity. I think the space complexity is $O(n)$ because I am creating $n$ copies of the 26 length array. Is there anything that I can do to reduce the amount of space I am using? I think this space will cumulate and add up.

You're making an assumption that these strings contain just letters. If there are spaces, digits, or letters with diacritics, then you'll end up with an ArrayIndexOutOfBoundsException.
isEqualCounts() is just a reimplementation of Arrays.equals(int[], int[]). If you choose not to use Arrays.equals(), then I suggest starting with assert counts1.length == counts2.length;.