Check if a permutation of a string can become a palindrome

Question

Write a method to test if a string meets the preconditions to become a palindrome.

Eg:

Input    | Output
mmo      | True  
yakak    | True  
travel   | False

I'm thinking of this approach:

1. Make a suffix tree for all permutation of T such that T$Reverse(T)#
2. Check for all permutation for same node

Am I missing anything?

Answer 1

Really all you're looking for is if all (or all but one) of the letters are paired off. As long as they are, then they will be able to be turned into a palindrome.

So it would be something like...

bool canBeTurnedIntoAPalindrome(string drome)
{
  // If we've found a letter that has no match, the center letter.
  bool centerUsed = false;
  char center;

  char c;
  int count = 0;

  // TODO: Remove whitespace from the string.

  // Check each letter to see if there's an even number of it.
  for(int i = 0; i<drome.length(); i++)
  {
    c = drome[i];
    count = 0;

    for(int j = 0; j < drome.length(); j++)
      if (drome[j] == c)
         count++;

    // If there was an odd number of those entries
    // and the center is already used, then a palindrome
    // is impossible, so return false.
    if (count % 2 == 1)
    {
      if (centerUsed == true && center != c)
        return false;
      else
      {
        centerused = true;
        center = c;   // This is so when we encounter it again it
                      // doesn't count it as another separate center.
      }
    }
  }
  // If we made it all the way through that loop without returning false, then
  return true;
}

This isn't the most efficient (it's counting letters as many times as it comes across them, even if they've been counted already) but it does work.