old_contents: # Time:  O(n * n!)
  # Space: O(n)
  
  class Solution(object):
      def generatePalindromes(self, s):
          """
          :type s: str
          :rtype: List[str]
          """
          cnt = collections.Counter(s)
          mid = [k for k, v in cnt.iteritems() if v % 2]
          chars = ''.join(k * (v / 2) for k, v in cnt.iteritems())
          return [''.join(half_palindrome + mid + half_palindrome[::-1]) \
                   for half_palindrome in self.permuteUnique(chars)] if len(mid) < 2 else []
      
      def permuteUnique(self, nums):
          result = []
          used = [False] * len(nums)
          self.permuteRecu(result, used, [], nums)
          return result
      
      def permuteRecu(self, result, used, cur, nums):
          if len(cur) == len(nums):
              result.append(cur + [])
              return
          for i in xrange(len(nums)):
              if not used[i] and not (i > 0 and nums[i-1] == nums[i] and used[i-1]):
                  used[i] = True
                  cur.append(nums[i])
                  self.permuteRecu(result, used, cur, nums)
                  cur.pop()
                  used[i] = False
  
  class Solution2(object):
      def generatePalindromes(self, s):
          """
          :type s: str
          :rtype: List[str]
          """
          cnt = collections.Counter(s)
          mid = tuple(k for k, v in cnt.iteritems() if v % 2)
          chars = ''.join(k * (v / 2) for k, v in cnt.iteritems())
          return [''.join(half_palindrome + mid + half_palindrome[::-1]) \
                  for half_palindrome in set(itertools.permutations(chars))] if len(mid) < 2 else []
  
new_contents: # Time:  O(n * n!)
  # Space: O(n)
  
  class Solution(object):
      def generatePalindromes(self, s):
          """
          :type s: str
          :rtype: List[str]
          """
          cnt = collections.Counter(s)
          mid = ''.join(k for k, v in cnt.iteritems() if v % 2)
          chars = ''.join(k * (v / 2) for k, v in cnt.iteritems())
          return [half_palindrome + mid + half_palindrome[::-1] \
                  for half_palindrome in self.permuteUnique(chars)] if len(mid) < 2 else []
      
      def permuteUnique(self, nums):
          result = []
          used = [False] * len(nums)
          self.permuteRecu(result, used, [], nums)
          return result
      
      def permuteRecu(self, result, used, cur, nums):
          if len(cur) == len(nums):
              result.append(cur + [])
              return
          for i in xrange(len(nums)):
              if not used[i] and not (i > 0 and nums[i-1] == nums[i] and used[i-1]):
                  used[i] = True
                  cur.append(nums[i])
                  self.permuteRecu(result, used, cur, nums)
                  cur.pop()
                  used[i] = False
  
  class Solution2(object):
      def generatePalindromes(self, s):
          """
          :type s: str
          :rtype: List[str]
          """
          cnt = collections.Counter(s)
          mid = tuple(k for k, v in cnt.iteritems() if v % 2)
          chars = ''.join(k * (v / 2) for k, v in cnt.iteritems())
          return [''.join(half_palindrome + mid + half_palindrome[::-1]) \
                  for half_palindrome in set(itertools.permutations(chars))] if len(mid) < 2 else []
  
subject: Update palindrome-permutation-ii.py