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.

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

-
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 letters = new Dictionary();

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

    //remove matched letters
    foreach(char c in str2.AsEnumerable())
    {
        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;
}

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

StackExchange Code Review Q#10849, answer score: 5