3517. Smallest Palindromic Rearrangement I

Problem Link

Description

---

You are given a palindromic string s.

Return the lexicographically smallest palindromic permutation of s.

 

Example 1:

Input: s = "z"

Output: "z"

Explanation:

A string of only one character is already the lexicographically smallest palindrome.

Example 2:

Input: s = "babab"

Output: "abbba"

Explanation:

Rearranging "babab" → "abbba" gives the smallest lexicographic palindrome.

Example 3:

Input: s = "daccad"

Output: "acddca"

Explanation:

Rearranging "daccad" → "acddca" gives the smallest lexicographic palindrome.

 

Constraints:

• 1 <= s.length <= 105
• s consists of lowercase English letters.
• s is guaranteed to be palindromic.

Solution

---

Python3

class Solution:
    def smallestPalindrome(self, s: str) -> str:
        N = len(s)
        counter = [0] * 26
        res = [""] * N
 
        for x in s:
            counter[ord(x) - ord('a')] += 1
 
        i, j = 0, N - 1
        odd = None
        cIndex = 0
        while i <= j and cIndex < 26:
            if counter[cIndex] == 0: 
                cIndex += 1
                continue
 
            while i < j and counter[cIndex] >= 2:
                res[i] = res[j] = chr(ord('a') + cIndex)
                i += 1
                j -= 1
                counter[cIndex] -= 2
 
            if counter[cIndex] == 1:
                odd = cIndex
                cIndex += 1
 
            if i == j and odd is not None:
                res[i] = chr(ord('a') + odd)
                break
 
        return "".join(res)