# Checking if two strings are permutations (anagrams) in Python

Practicing for my interview, I am working on some problems in Python.

This problem is to decide two strings are permutation (or anagrams) of each each other.

def is_permutation(first, second):
if len(first) != len(second):
return False
first_arr = [0 for i in range(256)] # ASCII size
second_arr = [0 for i in range(256)] # ASCII size
for i in range(len(first)):
first_arr[ord(first[i])] += 1
second_arr[ord(second[i])] += 1
if first_arr != second_arr:
return False
else:
return True


I feel this code can be more efficient, but I cannot make it. Can anybody give me advice or tip so that I can improve please?

The performance for the second line is $O(1)$, the fourth and fifth are $O(256)$ and your for loop on line six is $O(n)$. The code on line seven and eight are $O(1)$ and finally line nine is $O(n)$. Combining all this leads to $O(1 + 256 + n (1 + 1) + n)$, which simplify to $O(n)$.

The only time memory changes is on line four and five, where you use $O(256)$ more memory. And so this has $O(1)$ memory usage.

However, big O notation is just a guide. When you want to know what performs better test it.

If however you gave me this in an interview, I'd think you produce hard to read code. I would much prefer one of:

from collections import Counter

def is_permutation(first, second):
return sorted(first) == sorted(second)

def is_permutation(first, second):
return Counter(first) == Counter(second)


The former being $O(n\log(n))$ performance and $O(n)$ memory usage. The latter however is $O(n)$ in both performance and memory. 'Worse' than yours, but much easier to maintain.

From Sumit Raj's 2015 article 10 Neat Python Tricks Beginners Should Know, which I would classify as "more pythonic":

from collections import Counter
def is_anagram(str1, str2):
return Counter(str1) == Counter(str2)
>>> is_anagram('abcd','dbca')
True
>>> is_anagram('abcd','dbaa')
False

• It does seem like more pythonic! Jul 25, 2017 at 1:27

You could improve your code a little bit by using just one array instead of two to count a balance between character populations in both strings:

    balance_arr = [0 for i in range(256)] # ASCII size
for i in range(len(first)):
balance_arr[ord(first[i])] += 1
balance_arr[ord(second[i])] -= 1


Finally test if the array contains zeros only.

But it's still a character-level 'manual' operation.