# Anagram Checker

Two words are anagrams of each other if they contain the same letters, such as "pots == stop".

The easiest way to check is to sort both words, then compare. But that's an $O(n*log(n))$ solution and I'd like to find an $O(n)$ one.

1. Is this code $O(n)$? I only make one pass per string, but I use a hash Remove which is $O(n)$ by itself.

2. Is there a completely better way? Or can my code be optimized to run faster/cleaner?

public static bool AreAnagrams(string str1, string str2)
{
//lucky cases
if(str1 == str2)
return true;
if(str1.Length != str2.Length)
return false;

Dictionary<char, int> letters = new Dictionary<char, int>();

//put all the letters for str1 and their occurance in dictionary
foreach(char c in str1.AsEnumerable<char>())
{
if(letters.ContainsKey(c))
letters[c]++;
else
letters[c] = 1;
}

//remove matched letters
foreach(char c in str2.AsEnumerable<char>())
{
if(letters.ContainsKey(c))
{
letters[c]--;
if(letters[c] == 0)
letters.Remove(c);
}
//found a letter that wasn't in str1
else
return false;
}

//true if we added all the letters and removed them all
return letters.Values.Count == 0;
}

• Dictionary.Remove() is O(1), in the average case. – svick Apr 13 '12 at 6:54
• that's what I get for skimming wikipedia. So then my code is O(n) and as fast as it's going to get? – jb. Apr 13 '12 at 7:14
• For this kind of algorithms I find big O notation misleading. The algorithm is not going to escalate to large N's so, who cares for asymptotic complexity? O(2N) and O(10N) are both O(N), but for n < 10, O(N^2) beats O(10N) Are you going to check anagrams on long words? Don't think so... Bear in mind I'm not saying O(N^2) is not bad, I'm saying that for low N's, the linear factor actually matters because N's order is not that important, so big O is misleading. Correct me if I'm wrong! – kaoD Apr 20 '12 at 13:00

The Remove call is not necessary - in python:

def anagram(w1, w2):
from collections import Counter
counter = Counter()
for c in w1:
counter[c] += 1
for c in w2:
counter[c] -= 1
for count in counter.values():
if count != 0:
return False
return True


Yes, it's probably as fast as it gets (apart from a possible mistake that I'll explain). The average-case complexity of Remove is O(1), and it seems unlikely to me that you could skip any characters in a string since string comparison is O(n) and anagram checking is likely more complex than that. As a first guess, the asymptotic complexity of this algorithm is probably O(n)+O(n^2)=O(n^2) (n^2 because you are doing an O(n) operation for O(n) characters when calling Remove).

The average-case complexity of you algorithm is O(2n)=O(n), which is not bad at all for this problem. I think your implementation is likely to outperform the sorting one because the hash tables behave very well with a low amount of elements (if you mean anagrams in the sense of real words, you will have relatively small inputs).

Now, this line might not do what you intended:

if(str1 == str2)


According to the MSDN, this will compare the values of the strings, not their references, which is already an O(n) operation in itself:

For the string type, == compares the values of the strings.

If your intention was to compare the references (as an easy case), you must cast the strings to object and compare those:

if ((object)str1 == (object)str2)


It's important to note that it doesn't matter from the viewpoint of asymptotic complexity if you are doing an O(n) comparison here, since the O(n^2) later will dominate the complexity anyway. But for amortized complexity it matters, and that is important if you are dealing with small inputs.

• Better yet: object.ReferenceEquals(str1, str2). – ANeves thinks SE is evil Apr 13 '12 at 16:37
Dictionary<char, int> letters = new Dictionary<char, int>();


If you only need to support the 26 English letters, then using int array of size 26 will be more efficient and produce cleaner code.

• This is a great idea, I suggest you add the full solution I suspect the entire code will be very short and easy. – Leonid Apr 16 '12 at 0:05
• @Leonid, I'm hesitant to do that because I don't code in C#. The whole thing would be a one liner in my favored language, python. return Counter(w1) == Counter(w2) – Winston Ewert Apr 17 '12 at 19:20

The use of Remove is not needed though.

You can have something like

if(letters.ContainsKey(c) || letters[c] > 0)
letters[c]--;
else //found a letter that wasn't in str1
return false;

• Hmm, one extra unnecessary access. Perhaps if(!letters.ContainsKey(c) || letters[c]-- <= 0) { return false }? But this starts to get a bit criptic. – ANeves thinks SE is evil Apr 13 '12 at 16:39