Any Permutation is a Palindrome

Question:

Write an efficient function that checks whether any permutation of an input string is a palindrome.

Permutation is a way, especially one of several possible variations, in which a set or number of things can be ordered or arranged.

Palindrome is a word, phrase, or sequence that reads the same backward as forward.

method “permutationIsPalindrome(string)” should return true if palindrome is found.

For example:

“civic” should return true “ivicc” should return true “civil” should return false “livci” should return false

The original question was provided by interviewcake.com. www.Interviewcake.com Question

Breaking down the question a bit, your coded solution should accomplish and show the following:

• Permutations: find all unique varaitions of target input.
• Palindrome: Evaluate each permutation as palindrome.
• “permutationIsPalindrome(string)”: method accepts string input.

Assumptions:

A few item we can use to plan our solution

• String contains alphanumeric characters
• “permutationIsPalindrome” method returns true/false boolean if permutaion is a palindrome.

Solution (C++):

/* Function to evalute 'str' as a palindrome */
bool isPalindrome(std::string &s)
{
 return (std::equal( s.begin(), s.begin() + s.size()/2, s.rbegin() ));
}

/* Function to evalute all permutations 'str' as a palindrome */
bool permutationIsPalindrome(std::string &s){
  // Found palindrome flag
  bool foundPermutationAsPalindrome = false;

  // loop to find permutations of 'str' and evaluate each as palindrome
  do{
    if( isPalindrome(s) ){
      foundPermutationAsPalindrome = true;
    }
  }
  while( std::next_permutation(str.begin(), str.end() ) && foundPermutationAsPalindrome == false);

  // return palindrome flag
  return foundPermutationAsPalindrome;
}

int main(int argc, char const *argv){
 // Target string 
 std::string target_string("aabbcc");

 // Output 'permutationIsPalindrome' results to console
 std==cout << "Permutation of " << target_string << " is a palindrome: " << ( permutationIsPalindrome(target_string) ? "true" : "false" ) << std==endl;
  return 0;
}

Output:

Permutation of aabbcc is a palindrome: true

Happy coding!