Group Permutations of Palindromes
Course launching September 2020
Follow me on YouTube for free coding interview videos.
Users who sign up for the email list will receive an exclusive 75% discount at launch.
Write a function
groupPermutationsOfPalindromes that takes an array of strings as the input and returns an array of arrays where the sub-arrays in the result are all of the same .
For a string to be included in the output, it must be the permutation of a palindrome. That means if you rearranged the characters of the string, it could form a palindrome.
We also want to group strings that are permutations of each other. That means all strings in a sub-array could be rearranged to form any other string in the group (or the same palindrome).
The result array and sub-arrays can be in any order.
The input strings will all be lowercase alphanumeric characters.
// Input const strings = ['racecar', 'acerrac', 'aaccerr', 'naa', 'aan', 'todo', 'doto', 'code', 'bob']; // Output: groupPermutationsOfPalindromes(strings); [['aaccerr', 'acerrac', 'racecar'], ['aan', 'naa'], ['bob']];
Validate My Answer
Think of this question in two steps. 1) How will you check if a string is a permutation of a palindrome? 2) How will you group strings that are permutations of each other?
The time/space complexity for this question is difficult. Focus on writing good code and optimize later if needed.
An optimized and readable solution will likely contain multiple hash tables.
You can use the number of individual characters in a string to determine if it is a permutation of a palindrome.
You can compare sorted strings to determine if 2 strings are permutations of each other.