266 Palindromic Permutation

Problem Description:

Given a string, determine if a permutation of the string could form a palindrome.

For example, "code" -> False, "aab" -> True, "carerac" -> True.

That is that it reads the same forwards as backwards like “racecar”.

Hint:

Consider the palindromes of odd vs even length. What difference do you notice? Count the frequency of each character. If each character occurs even number of times, then it must be a palindrome. How about character which occurs odd number of times?

  #include <iostream>
  #include <unordered_map>
  using namespace std;

  bool palindromic(string word) 
  {
      unordered_map <char, int> wordCount;
      for (auto i : word) ++wordCount[i];

      if (word.size() - 1 % 2 == 0) // even
      {
          for (auto &i : wordCount)
          {
              if (i.second == 2) continue;
              else return false;
          }
          return true;
      }
      else // odd
      {
          int count = 0;
          for (auto &i : wordCount)
          {
              if (i.second == 2) continue;
              else if (i.second == 1) count++;
              if (count > 1) return false;
          }
          return true;
      }

  }

  int main()
  {
      cout << palindromic("aabbccddeefghf");
  }

Last updated