Problem Statement:
Palindrome Permutation: Given a string, write a function to check if it is a permutation of a palindrome.
A palindrome is a word or phrase that is the same forwards and backward.
A permutation is a rearrangement of letters. The palindrome does not need to be limited to just dictionary words.
Example
Input: vscodeocedvs
Output: true (e.g. vscodeedocsv)
Before directly jumping to the approach let’s define features of string which is a permutation of a palindrome.
For a string to be a “permutation of a palindrome” we need to have an even number of almost all characters, so that half can be on one side and half can be on the other side. At most one character (the middle character) can have an odd count.
e.g. vscodeocedvs have
v →2
s →2
c →2
o →2
d →2
e →2
Approach 1: Now since we know what are the features of a “permutation of a palindrome”. Implementing this algorithm is fairly straightforward. We use a hash table to count how many times each character appears. Then, we iterate through the hash table and ensure that no more than one character has an odd count.
Approach 2: We can improve Approach 1 with some smaller incremental improvements.
Instead of checking the number of odd counts at the end, we can check as we go along. Then, as soon as we get to the end of the iteration, we have our result.
The Time Complexity of both these solutions will be O(n), where n is the length of the string.
Below are the solutions using approach 2 in Javascript and Python3
Link Part #3: URLify
Thanks for reading
Feel free to share your suggestions in the comment.
Happy Coding!
