Cracking the Coding Interview - Determine if two strings are permutations of each other

1.3 Given two strings, write a method to decide if one is a permutation of the other


This is a super idiomatic and easy to understand approach. Python strings are immutable, so we can’t avoid the new string allocations caused by sorting. The runtime is O(nlogn).

def are_permutations(string_one, string_two):
    return sorted(string_one) == sorted(string_two)

Counting with a dictionary counter

Instead of using sorted inputs, we compare the occurrences of each character from both strings. Will this use more space?

I think it depends. Lets assume a unicode character set.

If we’re dealing with inputs that are mostly unique, likely take up more space compared to inputs with lots of duplication because we’ll have more keys and count values. There’s also the overhead of the hashmap itself.

def are_permutations(string_one, string_two):
    from collections import Counter
    return Counter(string_one) == Counter(string_two)

Counting with a list

If we assume ASCII input, we can get away with a counter with a smaller memory footprint than a hashmap: an array!

def are_permutations(string_one, string_two):
    list_counter = [0] * 256
    for s in string_one:
        idx = ord(s)
        list_counter[idx] += 1
    for s in string_two:
        idx = ord(s)
        list_counter[idx] -= 1
        if list_counter[idx] < 0:
            return False
    return True