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:

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?

  • $\begingroup$ 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. $\endgroup$ – Raphael Jun 14 '16 at 8:24
  • $\begingroup$ @IgnacioLebrero I added information in the question, you were right though as my examples weren't valid. $\endgroup$ – Andrew Raleigh Jun 14 '16 at 13:59
  • $\begingroup$ 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. $\endgroup$ – D.W. Jun 14 '16 at 16:04
  • $\begingroup$ 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? $\endgroup$ – D.W. Jun 14 '16 at 16:35
  • $\begingroup$ Added the information, I don't know where to go from there though. $\endgroup$ – Andrew Raleigh Jun 14 '16 at 20:06

If n is the number of words, it's impossible. It would mean that any roblem with just two words could be solved in constant time. But you could have two words of arbitrary equal length, and the time to confirm that one is the other reversed is unlimited if the length of the words is unlimited.

PS. Your edit changed this from a rather interesting problem to one that is really boring and trivial. You take an array with 26 counters, one for each letter, initialised to all zeroes. You go through the letters, and for each letter you increase the corresponding counter. When you are done, you check that there is at most one odd counter.

When you ask a question, it's only polite to take your time to state the question properly. Your original question has nothing whatsoever to do with the edited one.

And if you haven't figured it out: In a palindrome, the first and last letter, the second and second to last letter, and so on, are equal. Which means you have even numbers of each letter. There may be one letter in the middle (like in oxo) that doesn't have a match, or there may be none (like in otto). Which means at most one letter has an odd count. So to figure if a palindrome can be formed, just count the letters.

  • $\begingroup$ Sorry, n isn't the number of words. I edited the question to reflect it better. $\endgroup$ – Andrew Raleigh Jun 14 '16 at 0:07
  • 1
    $\begingroup$ @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? $\endgroup$ – D.W. Jun 14 '16 at 4:54
  • $\begingroup$ @AndrewRaleigh, please delete any comments that are no longer accurate or are obsolete. $\endgroup$ – D.W. Jun 14 '16 at 15:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.