July 28Medium

Smallest palindromic rearrangement i

String
Sorting
Counting Sort

Problem

You are given a palindromic string s. Return the lexicographically smallest palindromic permutation of s.

Solution

class Solution:
    def smallestPalindrome(self, s: str) -> str:
        letters = defaultdict(int)
        for letter in s:
            letters[letter] += 1
        a = ord("a")
        res = ""
        remaining = None
        for i in range(26):
            letter = chr(a+i)
            while letters[letter]:
                if letters[letter] == 1:
                    remaining = letter
                    letters[letter] = 0
                else:
                    res += letter
                    letters[letter] -= 2
        return res + (remaining or "") + res[::-1]