Group Permutations of Palindromes
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.
Breakdown
Approach and test strategy
Palindrome-permutation eligibility followed by multiplicity grouping
Read the approach, boundary cases, and complexity
First count each string’s characters and retain it only when at most one character has an odd count. That is the condition for rearranging the string into a palindrome. Then group retained strings by a canonical multiplicity signature. The input itself need not already read as a palindrome: naa and aan both qualify. Strings such as code, with several odd counts, are excluded rather than placed in another group.
Cases to check
- Check empty input and a qualifying string alone.
- Group naa with aan even though neither is displayed as a palindrome.
- Exclude todo, doto, and code; compare eligible groups independently of group and member order.
Cost model
Sorting each string to obtain a signature costs the sum of O(length · log length) over strings. The lowercase alphanumeric input domain also permits a fixed-alphabet frequency signature with linear total character work. First filter for at most one odd count; the returned groups retain only eligible input occurrences.
Programming languages for this lesson
Starter code and reference implementations are available in:
The editor shows which of these languages can run on this deployment.
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.
Group Permutations of Palindromes
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.