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)$?
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?