10
\$\begingroup\$

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?

\$\endgroup\$
  • 1
    \$\begingroup\$ It would be great if you would provide the benchmarking code, and some data about the benchmarking process so we could compare with own versions. \$\endgroup\$ – Incomputable Oct 18 '18 at 10:09
  • \$\begingroup\$ As a side note you can stop your final check loop as soon as odd_letter_count reaches two. \$\endgroup\$ – bipll Oct 18 '18 at 10:38
6
\$\begingroup\$

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.

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

  1. 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)) {
\$\endgroup\$
  • 1
    \$\begingroup\$ Bear in mind that auto copies the pair. An auto& may be more appropriate. \$\endgroup\$ – StoryTeller - Unslander Monica Oct 18 '18 at 4:48
  • \$\begingroup\$ Yeah, that's probably better. Actually, even better would be const auto& since we aren't modifying the value. I'll update my answer. \$\endgroup\$ – user1118321 Oct 18 '18 at 4:53
  • \$\begingroup\$ letter_count[c]++: you might add that pre-increment is better when you don't need the intermediate value \$\endgroup\$ – papagaga Oct 18 '18 at 7:28
  • \$\begingroup\$ The original post author should also have improved the second part of his algorithm: it isn't necessary to count all letters whose count is odd; he could break out as soon as 2 odd-count letters are detected. And +1 if he uses std::find_if for this. \$\endgroup\$ – papagaga Oct 18 '18 at 7:32
  • \$\begingroup\$ thanks for your input. i appreciate the feedback and yes i should definitely make it more legible! \$\endgroup\$ – mjl007 Oct 18 '18 at 18:48
3
\$\begingroup\$

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")
        ;
}
\$\endgroup\$
  • \$\begingroup\$ May be you could do counting of true elements and then comparing that with length being odd or not? Because then it would be kind of correspondence relationship. std::none_of is somewhat peculiar at the moment. Also, why not std::bitset? \$\endgroup\$ – Incomputable Oct 18 '18 at 10:06
  • \$\begingroup\$ Ah, I was going to mention bitset (trading speed for size) but forgot. I'll edit that in. Yes, you could go back to counting (arguably clearer, but you lose the early exit from the loop for the failure cases). What's peculiar about none_of? Is the fact that I capture by reference, or something else? \$\endgroup\$ – Toby Speight Oct 18 '18 at 10:09
  • \$\begingroup\$ std::none_of is really expressive here, and optimal since you return as soon as odd -= x is negative. \$\endgroup\$ – papagaga Oct 18 '18 at 10:11
  • \$\begingroup\$ @TobySpeight, I forgot about early return, sorry. \$\endgroup\$ – Incomputable Oct 18 '18 at 10:15
  • \$\begingroup\$ The only thing that might improve your code is to count the number of odd letter-counts while you're filling letter_count, and then compare it to s.length() % 2. For example: wandbox.org/permlink/4ADDXjaYI1NefIdJ \$\endgroup\$ – papagaga Oct 18 '18 at 10:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.