Valid anagram

Two words are anagrams if they use exactly the same letters. Count up for one word and down for the other.

Time O(n)Space O(1)Code C++, Python and C#

Watch it animatedStep through it, with the running line highlighted. Free with an account.

The idea

A fixed array of 26 counters is a tiny hash table for lowercase letters. If the second word ever needs a letter the first word did not supply, a counter goes negative.

Code

C++PythonC#

bool isAnagram(const string& a, const string& b) {
    if (a.size() != b.size()) return false;
    int count[26] = {0};
    for (char c : a) count[c - 'a']++;
    for (char c : b)
        if (--count[c - 'a'] < 0) return false;
    return true;
}

def is_anagram(a: str, b: str) -> bool:
    if len(a) != len(b): return False
    count = [0] * 26
    for c in a: count[ord(c) - ord('a')] += 1
    for c in b:
        count[ord(c) - ord('a')] -= 1
        if count[ord(c) - ord('a')] < 0: return False
    return True

public static bool IsAnagram(string a, string b) {
    if (a.Length != b.Length) return false;
    var count = new int[26];
    foreach (char c in a) count[c - 'a']++;
    foreach (char c in b)
        if (--count[c - 'a'] < 0) return false;
    return true;
}

Tips

Because the lengths are equal, no counter going negative means every counter ends at exactly zero.
For full Unicode text, switch the array for a Dictionary<char, int>.

In the .NET library

c - 'a' converts a lowercase letter to 0..25. Sorting both strings and comparing also works, at O(n log n).