Group Permutations of Palindromes Coding Interview Question | Skilled.dev
Interview Question

Group Permutations of Palindromes

Course launching November 17, 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.

Your subscription could not be saved. Please try again.
Your subscription was successful! 🤓

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

  1. 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?

  2. The time/space complexity for this question is difficult. Focus on writing good code and optimize later if needed.

  3. An optimized and readable solution will likely contain multiple hash tables.

  4. You can use the number of individual characters in a string to determine if it is a permutation of a palindrome.

  5. You can compare sorted strings to determine if 2 strings are permutations of each other.