Cracking the Code Interview Series: Check Permutation

Photo by Andreas Dress

Check Permutation: Given two strings, write a method to decide if one is a permutation of the other.

Examples

"abc" "bca" => True
"abc" "bca" => True
"abc" "aab" => False
"abc" "baca" => False

Questions

• Do the strings have the same length?
• Can I consider that the input will always be a string?
• The input could an empty string?

Solutions

Sorting & Comparing

def permutation(str1, str2):
    if len(str1) != len(str2):
        return False

    return sorted(str1) == sorted(str2)

We can compare the two strings after sorting the characters. If the sorted strings are equal, we return True, otherwise False.

• Space: O(1) (no new storage of the string)
• Time: O(NlogN) (because of the sorting)

Using the Set data structure

def permutation(str1, str2):
    if len(str1) != len(str2):
        return False

    first_set = set()
    second_set = set()

    for char in str1:
        first_set.add(char)

    for char in str2:
        second_set.add(char)

    return first_set == second_set

We always need to verify the length of the string first. Then create two sets, one for the first string, and the other for the second one.

Comparing the two sets, we know if they are equal or not, or in other terms, if it is a permutation or not.

• Space: O(N) (for each string we have a new set with N places - N is equal to the string length)
• Time: O(N) (just the str1 and str2 iteration)

Using a HashMap data structure

def permutation(str1, str2):
    if len(str1) != len(str2):
        return False

    characters = {}

    for char in str1:
        if char in characters:
            characters[char] += 1
        else:
            characters[char] = 1

    for char in str2:
        if char not in characters or characters[char] == 0:
            return False

        characters[char] -= 1

    return True

Using a hash map, we can map the characters from the first string to the count of this character in the string.

Iterating through the second string, we need to make sure that the character is in the hash map and the count is greater than zero. If it has, we just decrease the count for the character and move on. If it doesn't have, we can return False because it is not a permutation.

• Space: O(N) (new dictionary for the first string with N places - N is equal to the string length)
• Time: O(N) (just the str1 and str2 iteration)

Have fun, keep learning, and always keep coding!

My Twitter and Github