Determining if a string can be permuted to a palindrome I am going through Elements of Programming Interview by Aziz, Lee and Prakash one of the questions is how to determine if a string can be permuted to a palindrome. For example edified can be permuted to deified and now its a palindrome.

So my first implementation is this:

bool CanFormPalindrome(const string&amp; s) {
    std::unordered_map&lt;char, int&gt; letter_count;
    for(char c : s) {
      letter_count[c]++;
    }

    int odd_letter_count = 0;
    for(std::pair&lt;char, int&gt; letter : letter_count) {
      if(letter.second%2 != 0) {
        odd_letter_count++;
      }
    }

    return odd_letter_count &lt;= 1;
}


After I passed all the tests I saw the book's cleaner and sleeker implementation (compared to my implementation) which is:


bool CanFormPalindrome(const string&amp; s) {
  std::unordered_set&lt;char&gt; char_counter;
  for(char c : s) {
    if(char_counter.count(c)) {
      char_counter.erase(c);
    }
    else {
      char_counter.insert(c);
    }
  }
  return char_counter.size() &lt;= 1;
}



When I saw the time difference the tester timed my test at around 30 ms and the book's implementation at around 100 ms. I am wondering why my implementation is faster than the book's. My suspicion is that the calls to unordered_set's count, erase, and insert probably is the main bottle neck as opposed to just insert it just once and increment the value if it exists. 

Another question is if you were to ask this on an interview would you care about the space time complexity over speed? Obviously the unordered_set is far more space efficient than the unordered_map, but if its for greater performance gain can we take up more space?
I much prefer your solution. It's easy to read and straightforward. The difference in size between the 2 is probably not that much. Their code has an unordered_set with a few elements in it. Your code has an unordered_map with likely 26 elements in it. We're talking about 26 * 5 = 130 bytes vs. say 5 or 10 bytes for the set on average. On modern systems, this is not a difference in memory usage. It's all below 1KB. If you're working with some old or oddball hardware and that becomes an issue, you can deal with it then.

However, if I were to see this code in production, I would probably want the following changes:


I would opt for using auto instead of the long type name in this line:




for(std::pair&lt;char, int&gt; letter : letter_count) {


I'd make it:

for(const auto&amp; letter : letter_count) {


As mentioned in the discussion in the comments, making it a reference saves a copy of the pair and making it const lets a reader know that you aren't going to be modifying it.


I'd use more space between operators in the next line:




if(letter.second%2 != 0) {


would become:

if (letter.second % 2 != 0) {


It's just easier to read.


I might make that conditional into a named function just to make it clearer:




bool isOdd(const int x)
{
    return (x % 2) != 0
}

// ...
if  (isOdd(letter.second)) {