Interview challenge · easy · string, hash-map, sorting

Valid Anagram

The challenge

Given two strings s and t, return true if t is an anagram of s: it uses exactly the same letters, the same number of times, in any order.

Example

"anagram", "nagaram"  ->  true
"rat", "car"          ->  false

Idea: count letters instead of sorting. Add one for each letter of s, subtract one for each letter of t; it is an anagram if every count ends at zero. Time O(n), space O(1) for a fixed alphabet.

The solution

1# Valid Anagram - ayotl.dev
2def is_anagram(s, t):
3    if len(s) != len(t):
4        return False
5    # +1 for letters of s, -1 for t
6    count = {}
7    for a, b in zip(s, t):
8        count[a] = count.get(a, 0) + 1
9        count[b] = count.get(b, 0) - 1
10    # anagram: every count is back to 0
11    return not any(count.values())
12
13
14print(is_anagram("anagram", "nagaram"))
15print(is_anagram("rat", "car"))

$ python3 valid_anagram.py

True

False

The video

Watch on YouTube →