3517. Smallest Palindromic Rearrangement I

String
Greedy
Counting
Sorting

TIME

O(n)

SPACE

O(n)

Intuition

A palindrome is fully determined by its left half (and a possible middle character). Because s is already palindromic, every character count is even except at most one, exactly the condition needed to form a palindrome. To make the whole palindrome lexicographically smallest, make its left half as small as possible: place characters in ascending order, using half of each character's count. The right half is then forced (it must mirror the left), and the lone odd character sits in the middle.

Approach

Count each character.
Build the left half by appending count[c] // 2 copies of each character c in a..z order.
If one character has an odd count, that single leftover is the middle.
Result = left + middle + reverse(left).

Complexity

Time: O(n), counting and building each half once (26-letter alphabet is constant)
Space: O(n), the output string

Edge Cases

Single character → it's the middle, empty halves → itself (Example 1)
Odd length → exactly one character has an odd count → middle
Even length → no middle
All same character → already the smallest palindrome
Input guaranteed palindromic, so at most one odd count is assured

Code

from collections import Counter


class Solution:
    def smallestPalindrome(self, s: str) -> str:
        """
        3517. Smallest Palindromic Rearrangement I
        Time: O(n)
        Space: O(n)
        """
        cnt = Counter(s)

        left = []
        middle = ""
        for ch in sorted(cnt):
            left.append(ch * (cnt[ch] // 2))
            if cnt[ch] % 2 == 1:
                middle = ch  # the single odd character sits in the center

        left_half = "".join(left)
        return left_half + middle + left_half[::-1]

/**
 * 3517. Smallest Palindromic Rearrangement I
 * Time: O(n)
 * Space: O(n)
 */
class Solution {
    public String smallestPalindrome(String s) {
        int[] cnt = new int[26];
        for (int i = 0; i < s.length(); i++) {
            cnt[s.charAt(i) - 'a']++;
        }

        StringBuilder left = new StringBuilder();
        char middle = 0;
        for (int c = 0; c < 26; c++) {
            for (int k = 0; k < cnt[c] / 2; k++) {
                left.append((char) ('a' + c));
            }
            if (cnt[c] % 2 == 1) {
                middle = (char) ('a' + c); // the single odd character sits in the center
            }
        }

        String leftHalf = left.toString();
        String rightHalf = left.reverse().toString();
        return middle == 0 ? leftHalf + rightHalf : leftHalf + middle + rightHalf;
    }
}