Detecting if two strings are anagrams

Question

I am trying to write a function that detects if two strings are anagrams of one another; more specifically, I want the function to be linear in its time complexity (\$O(n)\$ where \$n\$ is the length of the given string(s)).

My approach for doing this is to essentially maintain a dictionary of the characters and their occurrences. For the first string, I increment the key corresponding to a character; for the second string, I decrement the key corresponding to the character. At the end, I check if every key in the dictionary has a value of 0: if so, the number of chars in the first string 'cancel out' those in the second, which means the occurrences are equal and the strings are anagrams. Else, the strings are not anagrams.

Does this function run in linear time? When I iterate through the strings to add to the dictionary, that's linear I think. But does checking every key in the dictionary afterwards take linear time as well? If so, this would be quadratic in its complexity. How would I resolve the issue then, since I think to make this function linear the dictionary must be used but in a smarter way.

  def are_anagrams(s1,s2):
      """Returns True if s1 and s2 are anagrams of one another.
         False otherwise.
         Precondition: s1, s2 are both strings """

    if len(s1) != len(s2): #automatic failure
        return False 

    #same length
    d = {} 
    index = 0 
    bound = len(s1) 
    while index < bound: #iterate through each string and its chars
        s1_char = s1[index]
        s2_char = s2[index]

        #update d for s1
        if s1_char not in d:
            d[s1_char] = 1
        elif s1_char in d:
            d[s1_char] += 1

        #update d for s2
        if s2_char not in d:
            d[s2_char] = -1 
        elif s2_char in d:
            d[s2_char] -= 1


        index += 1

    for key in d:
      if d[key]: #if d[key] != 0, one string has an additional/fewer 
                 #character
          return False
    return True

Answer 1

As @Graipher suggested, why bother do this yourself when Python's builtins could give you the answer on a golden plate?

from collections import Counter 


def are_anagrams(str1, str2):
    """Return True if str1 and str2 are anagrams and False otherwise.""" 
    return Counter(str1) == Counter(str2)

Some examples:

are_anagrams('123', '321')
True
are_anagrams('', '')
True
are_anagrams('aabbcc', 'bacac')
False

And that's it. Furthermore it's \$O(n)\$ as you wanted.

And don't think it's something hard to grasp underneath, it's basically just a dictionary with its items as keys and counts as values.

---

Regarding your code, there are a few style issues that I'd like to point out:

• avoid useless/obvious comments like # automatic failure
• use 4 spaces per indentation level. (always - not two, not one, not 10. Always 4)
• there should be one space after the comma (def are_anagrams(s1, s2):)
• don't forget the dot at the end of the docstring (OCD, sorry)
• you should always put a space after #

Instead of doing this:

for key in d:
    if d[key]:
        ...

You can do (look also for iteritems() for other python versions):

for key, value in d.items():
    if value:
        ...

To iterate over a string's chars it's recommended to use Python's builtin enumerate (instead of that while) like this:

for index, char in enumerate('test'):
    print('char: {}; index: {}'.format(char, index))

char: t; index: 0
char: e; index: 1
char: s; index: 2
char: t; index: 3

Answer 2

As @MrGrj said in the comments, you should be using the built-in collections.Counter for this:

from collections import Counter

def are_anagrams(str1, str2):
    return Counter(str1) == Counter(str2)

This is \$\mathcal{O}(n+m+min(n, m)) = \mathcal{O}(k)\$, where \$n = \$len(str1) and \$m = \$len(str2). The equivalence comparison will need to compare all keys, but it should fail as soon as it finds one key not in the other dictionary, therefore it is \$\mathcal{O}(min(n, m))\$. So the overall run time is linear.

Answer 3

Yes as others suggested the best and cheapest way. Although if you wouldn't like to use collections then you could do something like this too.

def are_anagrams(str1, str2):
    if len(str1) == len(str2):
        return sorted(str1) == sorted(str1)

For large anagrams this isn't optimal but its still one liner and pure python no collections. Anyway using a dictionary is far cheaper then using sorting on strings (at least I think so).