Check if one string is a permutation of another using Python

The code below is an attempt at a solution to an exercise from the book "Cracking the Coding Interview."

I believe that the worst case time complexity of the code below is \$O(n)\$, where n is the length of each string (they should be the same length since I am checking if there lengths are equal) and the space complexity is \$O(n)\$.

Is this correct? In particular does checking the length of each string take \$O(1)\$ time?

def is_permutation(first_string, other_string):
    if len(first_string) != len(other_string):
        return False

    count_first = {}
    count_other = {}

    for char in first_string:
        if char in count_first.keys():
            count_first[char] += 1
        else:
            count_first[char] = 1

    for char in other_string:
        if char in count_other.keys():
            count_other[char] += 1
        else:
            count_other[char] = 1

    for char in count_first.keys():
        if char not in count_other.keys():
            return False
        elif count_first[char] != count_other[char]:
            return False

    return True

Yes, len(str) should be O(1) in Python. (Good question!) Each of your for loops is O(n), so your whole function is O(n).

Your counting loops could be written more compactly as

for char in first_string:
    count_first[char] = 1 + count_first.get(char, 0)

The epilogue could be simplified to

return count_first == count_other

It pays to get familiar with the standard Python library, though. Your entire function could be more simply implemented as

from collections import Counter

def is_permutation(a, b):
    return len(a) == len(b) and Counter(a) == Counter(b)

… where len(a) == len(b) is an optional optimization. Writing less code simplifies maintenance and tends to create fewer opportunities for introducing bugs (as in Rev 2 of your question).

StackExchange Code Review Q#140807, answer score: 18