Test whether two strings are anagrams of each other 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
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.