Coding Puzzle: Anagram Check

• Difficulty: Easy

Problem Definition

Given 2 strings, determine if the strings are anagrams of each other.

Examples

Some test cases to verify our solution.

assert are_anagrams("tea", "ate")
assert are_anagrams("ate", "eat")
assert not are_anagrams("eat", "beat")
assert not are_anagrams("eat", "bat")

Solution

We will count the characters in one string and then decrement those counts while traversing through the second string. If the second string contains a character that is not in the count, then we'll return False. If one of those characters has a remaining count after we've processed the second string, then we will also return False. Otherwise, we'll return True.

def are_anagrams(s1, s2):
    if len(s1) != len(s2):
        return False
    counts = dict()
    for c in s1:
        counts[c] = counts.get(c, 0) + 1
    for c in s2:
        if c not in counts:
            return False
        counts[c] -= 1
        if counts[c] == 0:
            del counts[c]
    if counts:
        return False
    return True

Complexity

Let $n = $ max(len(s1), len(s2)).

Runtime complexity should be $O(n)$ since we might traverse both strings in the worst case.

Space complexity should be $\Theta(n)$.