Acquiring indices for anagrams of an input string

Question

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))
            allAnas.add(c);
    }
    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.

Answer 1

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;.

A more robust strategy, which doesn't rely on the assumption that the text is purely alphabetic, would be to check whether each sorted array of characters matches the sorted array of characters of the reference string.

You could optionally add a quick-but-crude check by calculating a "summary" or "fingerprint" of each string that consists of its length and, say, the sum of all its characters. Any string whose fingerprint is different from the fingerprint of the reference could be immediately rejected. The strings with matching fingerprints could then be checked more thoroughly.