Determining if a string can be permuted to a palindrome

Question

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& s) {
    std::unordered_map<char, int> letter_count;
    for(char c : s) {
      letter_count[c]++;
    }

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

    return odd_letter_count <= 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& s) {
  std::unordered_set<char> char_counter;
  for(char c : s) {
    if(char_counter.count(c)) {
      char_counter.erase(c);
    }
    else {
      char_counter.insert(c);
    }
  }
  return char_counter.size() <= 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?

Answer 1

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:

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

for(std::pair<char, int> letter : letter_count) {

I'd make it:

for(const auto& 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.

2. 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.

3. 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)) {

Answer 2

Updating an element in a collection is significantly faster than inserting or removing an element, as you've observed. I think your code is better than the book's version.

We can be even more efficient by using a std::array if we convert characters to unsigned char for the indexing - then there's no insertion of elements required. The flip side is that we check all possible characters, even those that never appear in the string; I'm guessing that's a small cost compared to allocating memory.

---

One improvement I'd recommend is to note that counts can't be negative:

std::unordered_map<char, unsigned int> letter_count;

(That also deals nicely with overflow, which is defined for unsigned types, and consistent with what we need).

---

Alternatively, you might simply toggle the value using XOR, rather than counting:

for (char c: s) {
  letter_count[c] ^= 1;
}

Then we only have to compare equality when looking for odd counts.

Using only one bit per possible character would allow us to use std::bitset as an alternative to std::array. That trades some speed for lower storage requirement.

---

A slight improvement - we know the original string's length - if it's even, then there should be no odd counts at all, so we can exit the checking loop earlier.

#include <string>
#include <unordered_map>

bool CanFormPalindrome(const std::string& s) {
    std::unordered_map<char, bool> letter_count;
    for (char c: s) {
      letter_count[c] ^= 1;
    }

    int odd_letter_count = s.length() % 1;
    for (const auto& letter: letter_count) {
        if ((odd_letter_count -= letter.second) < 0) {
            return false;
      }
    }

    return true;
}

---

Here's a version using std::array, and a standard algorithm instead of a loop:

#include <string>
#include <array>
#include <algorithm>
#include <climits>

bool CanFormPalindrome(const std::string& s) {
    std::array<bool, UCHAR_MAX> letter_count = {};
    for (unsigned char c: s) {
        letter_count[c] ^= 1;
    }

    int odd = s.length() % 2;
    return std::none_of(letter_count.begin(), letter_count.end(),
                        [&odd](auto x) { return (odd -= x) < 0; });
}

The std::none_of() function returns early in the same way as the loop above. Also (though unlikely to be helpful here), from C++17 onwards it has an option to parallelize its execution.

---

And some tests (for all versions of the code):

int main()
{
    return
        + !CanFormPalindrome("")
        + !CanFormPalindrome("a")
        +  CanFormPalindrome("ab")
        +  CanFormPalindrome("abcb")
        + !CanFormPalindrome("abab")
        + !CanFormPalindrome("edified")
        ;
}