Optimizing Java Anagram checker (compare 2 strings)

Question

An anagram is like a mix-up of the letters in a string:

pots is an anagram of stop

Wilma is an anagram of ilWma

I am going through the book Cracking the Coding Interview and in the basic string manipulation there's the problem:

write a method to check if two strings are anagrams of each other.

My method uses StringBuffer instead of String because you can .deleteCharAt(index) with StringBuffer/StringBuilder.

public boolean areAnagrams(StringBuffer s1b, StringBuffer s2b) {

    for (int i=0; i<s1b.length(); ++i) {
        for (int j=0; j<s2b.length(); ++j) {

            if (s1b.charAt(i) == s2b.charAt(j)) {

                s1b.deleteCharAt(i);
                s2b.deleteCharAt(j);

                i=0;
                j=0;
            }
        }
    }

    if (s1b.equals(s2b)) {
        return true;
    } else
        return false;

}

I iterate over every character in s1b and if I find a matching char in s2b I delete them both from each string and restart the loop (set i and j to zero) because the length of the StringBuffer objects changes when you .deleteCharAt(index).

I have two questions:

• Should I use StringBuilder over StringBuffer (in Java)?
• How can I make this faster?

In regards to fasterness:

This method is good in that it doesn't require any additional space, but it sorta destroys the data as you're working on it. Are there any alternatives that I have overlooked that could potentially preserve the strings but still see if they are anagrams without using too much external storage (i.e. copies of the strings are not allowed -- as a challenge)?

And, if you can use any sort of storage space in addition to this, can one lower the time complexity to \$O(n)\$ (technically \$O(2n)\$) instead of \$O(n^2)\$?

Also, the above code might not compile because I just wrote it from scratch in here; sorry if it's bugg'd.

Answer 1

Start with a simple, easy to understand version. Try to reuse API functions.

import java.util.Arrays;
... 

public boolean areAnagrams(String s1, String s2) {
    char[] ch1 = s1.toCharArray();
    char[] ch2 = s2.toCharArray();
    Arrays.sort(ch1);
    Arrays.sort(ch2);
    return Arrays.equals(ch1,ch2);
}

Of course this is not the fastest way, but in 99% it is "good enough", and you can see what's going on. I would not even consider to juggle with things like deleted chars in StringBuilder if there were no serious performance problem.

Answer 2

This is essentially asking you to compare if two sets are equivalent, thinking of the strings as a set of characters where the order doesn't matter.

For an O(n) runtime algorithm, you could iterate through the first string, and count the number of instances of each letter. Then iterate over the second string and do the same. Afterwards, make sure the counts match.

To save a little bit of storage, use the same array for both counts; while iterating the first string, increment the count once for each letter. When iterating the second, decrement. Afterwards, make sure each letter count is zero.

When running this algorithm over generic sets of objects, one might store the counts in a dictionary keyed off the object's hashcode. However, because we're using a relatively small alphabet, a simple array would do. Either way, storage cost is O(1).

Cosider the following pseudo-code:

function are_anagrams(string1, string2)

    let counts = new int[26];

    for each char c in lower_case(string1)
        counts[(int)c]++

    for each char c in lower_case(string2)
        counts[(int)c]--

    for each int count in counts
        if count != 0
            return false

    return true

Answer 3

how can I make this faster?

Perform a preliminary check if both strings have equal lengths. But that doesn't change the Big-O complexity of the algorithm though.

Your algorithm is O(a * b) * (a+b), where a and b are the lengths of your input strings. The last (a+b) are the two deleteCharAt(...) operations, making it in all a O(n^3) algorithm. You could bring that down to O(n) (linear) by creating a frequency map of your strings, and comparing those maps.

A demo:

import java.util.HashMap;
import java.util.Map;

public class Main {

    public static boolean anagram(String s, String t) {
        // Strings of unequal lengths can't be anagrams
        if(s.length() != t.length()) {
            return false;
        }

        // They're anagrams if both produce the same 'frequency map'
        return frequencyMap(s).equals(frequencyMap(t));
    }

    // For example, returns `{b=3, c=1, a=2}` for the string "aabcbb"
    private static Map<Character, Integer> frequencyMap(String str) {
        Map<Character, Integer> map = new HashMap<Character, Integer>();
        for(char c : str.toLowerCase().toCharArray()) {
            Integer frequency = map.get(c);
            map.put(c, frequency == null ? 1 : frequency+1);
        }
        return map;
    }

    public static void main(String[] args) {
        String s = "Mary";
        String t = "Army";
        System.out.println(anagram(s, t));
        System.out.println(anagram("Aarmy", t));
    }
}

which prints:

true
false

Answer 4

I'm going to answer this a bit more meta:

Seeing this question I ask myself: What does the interviewer want to know from me?

Does he expect

• a low-level, highly optimized algorithm (as you are attempting)
• or does he want to see, that I can apply the standard Java API to the problem (as Landei suggests)
• or maybe something in between, like the optimized implementation and use of a multi-set/counted set/bag (as Bart and Scott do)

Possibly the interviewer just expects you to discuss exactly that with him, so that he sees that you know that these alternatives exist and which advantages and disadvantages they have.

Answer 5

Using Guava's MultiSet, you can get some very readable and concise code:

public static boolean areAnagrams(String s1, String s2) {
  Multiset<Character> word1 = HashMultiset.create(Lists.charactersOf(s1));
  Multiset<Character> word2 = HashMultiset.create(Lists.charactersOf(s2));    
  return word1.equals(word2);
}

Answer 6

deleteCharAt(index) needs to shuffle the characters after index across, so you might be better off iterating over the text starting from the end.

If you are comparing many strings against each other, I would probably start by creating (and caching) copies of the strings but with their characters sorted. This would allow you to identify anagrams with a standard string comparison. As an added benefit, you can use the string with sorted characters as a hash table key making it quick and easy to find anagrams in a long list.

Answer 7

// in Java this would be an unusual signature
public boolean areAnagrams(StringBuffer s1b, StringBuffer s2b) {

for (int i=0; i<s1b.length(); ++i) {
    for (int j=0; j<s2b.length(); ++j) {
        // what could you do if the condition evaluates fo false here?
        if (s1b.charAt(i) == s2b.charAt(j)) {
            // ouch.  ask yourself what might be happening inside this JDK method
            // best case it bumps an offset, worst case it reallocs the backing array?
            s1b.deleteCharAt(i);
            s2b.deleteCharAt(j);

            // double ouch.  one failure mode for fiddling with the loop var would be infinite loop
            // avoid this
            i=0;
            j=0;
        }
    }
}

// if you have reached this line of code, what else do you know about s1b and s2b?
if (s1b.equals(s2b)) {
    return true;
} else
    return false;
}

Answer 8

I like the guava based response but here is a histogram based answer for completion sake. It builds a single histogram to capture differences in two words for the given character set (in this case, assumes 8-bit) and uses the histogram later to identify whether two words are Anagrams.

public boolean areAnagrams(String word1, String word2) {
    int[] counts = new int[256]; /*assuming 8-bit character set */

    if(word1.length() != word2.length())
        return false;

    int inputLength = word1.length();

    for(int index=0; (int)word1.charAt(index) > 0 && (int)word2.charAt(index) > 0; index++ ) {
        counts[(int)word1.charAt(index)] ++;
        counts[(int)word2.charAt(index)] --;
    }

    for(int index=0; index < inputLength; index++ )
        if(counts[index] > 0)
           return false;
    return true;
}

Answer 9

Assume that we want to check Str1 and Str2 if they are anagrams or not

public boolean checkAnagram(String s1 , String s2 ) {
    int i=0;
    int j=0;

    // no need to check if that j < s2.length() 
    // because the two strings must be that the same length.

    while(i < s1.length()) { 

        if(s1.indexOf(s2.charAt(j) < 0 || s2.indexOf(s1.charAt(i)) < 0 ) 
            return false;

        i++;
        j++;
    } // end of While

    return true;
}// end of Check Anagram Method. the Big-Oh is O(n log n)

Answer 10

I think this works with a complexity O(2n). This can be done with an array level operations.
The solution uses a buffer array of size 256 (assuming string contains chars with ASCII value less than 256), ASCII value of each char is used as array index.

First loop: increments the array position of each characters.

Second loop: Check any of the positions are zero, that means the character is not present in the first string or it presents more number of times than the first one.

public static boolean isAnagram(String str1, String str2){
    if(str1.length() != str2.length()){ return false;}
    int[] buffer = new int[256]; 
    for(char ch : str1.toCharArray()){
        buffer[ch]++;
    }
    for(char ch : str2.toCharArray()){
        if(buffer[ch]==0) return false;
        buffer[ch] = (buffer[ch] > 0)?(buffer[ch] - 1 ): -1 ;   
    }
    return true;
}