Problem 🤔

Given two strings, write a function to determine if the first string is a permutation of the second.

Note

• Spaces don’t count!

Real World Applications 🌎

You won’t be dealing with permutation validation this often in real life, don’t worry! However, this is a good exercise in finding duplicate occurrences.

The Finer Details 🔎

There are two ways to go about this. One that optimizes runtime on account of space and the other that optimizes for space. This is always a great point to start a discussion with your interviewer to understand what we’re aiming for.

Space Complexity Optimized Solution 💡

Complexity Analysis 🧮

Time complexity

O(nlogn)

Sorting string and one loop over string.

Space complexity

O(1)

Constant amount of auxillary variables used.

Note

• In python, strings are immutable, so the sort function actually allocates and returns new strings! Technically, the space complexity here is O(n), but this is language specific. Make sure to mention this to your interviewer!

This works! But can we do better?

Time Complexity Optimized Solution 💡

If both strings hold identical chars, they are a permutation of one another, regardless of the order! Let’s use an auxillary data structure to document characters seen and their occurrences. If all chars appear equally we know we have a palindrome!

Complexity Analysis 🧮

Time complexity

O(n)

Loop over input once

Space complexity

O(n)

Constant amount of auxillary variables used.

Takeaways 🎉🥳

When dealing with strings and permutations we can try and use the common techniques of:

• Sorting the string
• Auxillary data structures to keep track of seen chars

Resources 📚 💻

Cracking the Coding Interview (CTCI) 1.2