# Cracking the Code Interview Series: Check Permutation

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:

for char in str2:

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)