Test whether two strings are anagrams of each other

Question

What is the time/space complexity of this algorithm which checks if two strings are anagrams? My guess is that time is \$O(n)\$ and space \$O(1)\$ but I am not sure. Can it be improved?

def anagram(str1, str2):
 s1 = list(str1)
 s2 = list(str2)
 freq1 = {}
 freq2 = {}
 for pos in s1:
 freq1[pos] = s1.count(pos)
 for pos in s2:
 freq2[pos] = s2.count(pos)
 if freq1 == freq2:
 return True
 else:
 return False

• ChatterOne: If n is the number of letters in your strings, you're going to have an amount of keys in your hash which is the same as the amount of letters, so space is also \$O(n)\$
• hjpotter92: A sorted list would be equal for both.

Answer 1

You take a string, and instantly make a list from it, and so space is at least \$O(n)\$. s1.count(pos) is an \$O(n)\$ operation, and is in a loop that loops \$n\$ times, and so the loop is \$O(n^2)\$. To make the loops \$O(n)\$ you just need to add 1 to the amount, and use a defaultdict to default everything to 0.

from collections import defaultdict
def anagram(str1, str2):
 freq1 = defaultdict(int)
 freq2 = defaultdict(int)
 for char in str1:
 freq1[char] += 1
 for char in str2:
 freq2[char] += 1
 return freq1 == freq2

---

This can however be simplified to use collections.Counter. And so you can use:

from collections import Counter
def anagram(str1, str2):
 return Counter(str1) == Counter(str2)

---

And so both the above have \$O(n)\$ time and space complexity.

• Gareth Rees: The \$\Omega(n^2)\$ behaviour can't arise in this case (at least not in CPython), because all characters have distinct hashes.
• Peilonrayz: @GarethRees My bad, I didn't know. Also, do you know of a source stating that, that I could learn from?
• Gareth Rees: It's not documented anywhere, but it's a natural consequence of the implementation — see _Py_HashBytes. That's why I wrote "(at least not in CPython)" — another Python implementation might implement hashes differently and then it might not be true.
• Peilonrayz: @GarethRees Thank you for the link, I'll have to look into that, :)
• user1685095: First time I saw Counter used. Cool!