# Is there a way to determine if a collection is a palindrome within a time bound?

I'm learning about data structures, and there's a problem where, given a collection of words $X = (x_1, x_2, \dots, x_n)$ (can include duplicates), I have to find out if it's a palindrome or not. I'm looking for an algorithm that runs in $O(c n)$ time, where $c$ is the maximum length of any word in $X$.

A collection is a palindrome if all the characters in $X$ can be rearranged into a palindrome. For example, $X =$ (nun, ap, pa) is a palindrome (since apnunpa is) and (run, urn, appa) is a palindrome (since apurnnrupa is). The characters can be re-ordered, even within a word. The alphabet is also limited and finite.

I read about palindrome trees, but the question can be answered with a basic data structure. Any ideas on how to design an algorithm with worst-case running time $O(n)$?

Original Question:

My main question is what implementation would be best for find if a collection is a palindrome. The best one I found to remain within the time constraints would be a binary heap. What I don't get is how I can check if the characters can form a palindrome or not. My normal implementation would be to form combinations of all then check if its a palindrome, which is O(n!). Any ideas on what method works?

• Hint: imagine you have a two-sided finite automaton, i.e. one where one head moves left-to-right and the other right-to-left. – Raphael Jun 14 '16 at 8:24
• @IgnacioLebrero I added information in the question, you were right though as my examples weren't valid. – Andrew Raleigh Jun 14 '16 at 13:59
• OK. 1. You should also edit the question to include the guarantee that the alphabet is a constant size, as that changes the answer. 2. My next question is: What have you tried? We want to help you understand concepts, not do your exercise for you. – D.W. Jun 14 '16 at 16:04
• 1. Please edit the question to include that information and all other relevant information -- don't put it in the comments. Comments exist only to help you improve the question. We want all clarifications to be part of the information in the question. Readers shouldn't have to read the comments (and comments can be deleted at any time). 2. OK, so you're trying a binary heap. What have you found? Does it work? Does it not work? Where do you get stuck? Do you have a specific question about that approach? – D.W. Jun 14 '16 at 16:35
• Added the information, I don't know where to go from there though. – Andrew Raleigh Jun 14 '16 at 20:06

• @AndrewRaleigh, I don't follow. You say the set of words is $x_1,\dots,x_n$. That implies that $n$ is the number of words. And I don't see anything in the question stating to the contrary. How should we square that with your statement that $n$ isn't the number of words? – D.W. Jun 14 '16 at 4:54