What is the difference between palindrome permutation and permutation? [closed]

by

These two questions typically differ based on how they’re framed. Usually, the string permutation question is asked as

Given a string w and a string x, check whether w is a permutation of x.

In that sense, you know what both strings are, and you just need to see whether the character counts match (or whether they have the same sorted order, etc.)

The palindrome permutation problem is typically asked as

Given a string w, determine whether there is a string x where x is a palindrome and w is a permutation of x.

So in this case, you’re just given a single string w and need to figure out whether somewhere out there there’s a palindrome that it’s a permutation of. This problem is different, since you don’t have an explicit target string to compare against and you need to have the creative insight of counting up the counts of each character to see whether there are exactly zero or one characters that appear an odd number of times.

The general problem of “is w a permutation of x?” ceases to be interesting if you reframe it as “is w a permutation of some string?” because the answer is an immediate “yes,” and the problem of “is w a permutation of some palindrome?” loses its charm if you reframe it as “is w a permutation of the palindrome x?” because it’s essentially the same as the general permutation problem.

More Related Contents:

  1. Fast String Hashing Algorithm with low collision rates with 32 bit integer [closed]
  2. Splitting a string by a character
  3. C++ string::find complexity
  4. Are there any better methods to do permutation of string?
  5. Similar String algorithm
  6. How to find and replace all occurrences of a substring in a string?
  7. how to split a string for equation
  8. std::stoi() takes first number in string?
  9. Remove text in-between delimiters in a string (using a regex?)
  10. How do I properly use std::string on UTF-8 in C++?
  11. how to pre-allocate memory for a std::string object?
  12. How to change string into QString?
  13. Implicit conversion from char** to const char**
  14. Assign a nullptr to a std::string is safe?
  15. Comparing strings lexicographically
  16. Copy a streambuf’s contents to a string
  17. c++ sizeof( string )
  18. Why can’t the switch statement be applied to strings?
  19. Fast n choose k mod p for large n?
  20. Inverting a 4×4 matrix
  21. Print 2-D Array in clockwise expanding spiral from center
  22. std::back_inserter for a std::set?
  23. How to rotate a N x N matrix by 90 degrees? [closed]
  24. What is the difference between string::at and string::operator[]?
  25. When did C++ compilers start considering more than two hex digits in string literal character escapes?
  26. What is the simplest way to convert char[] to/from tchar[] in C/C++(ms)?
  27. How to write an object to file in C++
  28. A possible algorithm for determining whether two strings are anagrams of one another? [closed]
  29. How to convert int to string in C++
  30. Assign a string literal to a char* [duplicate]

Leave a Comment